BOJ : https://www.acmicpc.net/problem/12101

github : https://github.com/junho0956/Algorithm/blob/master/12101/12101/%EC%86%8C%EC%8A%A4.cpp

 

기본 9095번같은 경우 dp를 사용했었지만 사실 n의 사이즈가 dp를 사용하지 않아도 되는 문제입니다.

이 문제의 경우 dp를 사용하지 않고, dfs간에 string 을 추가시켜주면서 해결하였습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<string> v;
 
int dfs(int num, string str) {
 
    if (num < 0) return 0;
    if (num == 0) {
        v.push_back(str);
        return 1;
    }
 
    int res = 0;
 
    for (int i = 1; i <= 3; i++) {
        res += dfs(num - i, str+=(i+'0'));
        str.pop_back();
    }
 
    return res;
}
 
int main() {
    int n, k; cin >> n >> k;
    dfs(n, "");
    sort(v.begin(), v.end());
 
    if (k > v.size()) cout << "-1";
    else {
        string ans = "";
        for (int i = 0; i < v[k-1].size(); i++) {
            ans += v[k-1][i];
            ans += '+';
        }
        ans.pop_back();
        cout << ans;
    }
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 15989번 1, 2, 3 더하기 4  (0) 2020.02.18
BOJ 15988번 1, 2, 3 더하기 3  (0) 2020.02.18
BOJ 11403번 경로 찾기  (0) 2020.02.17
BOJ 11046번 팰린드롬??  (0) 2020.02.16
BOJ 13275번 가장 긴 팰린드롬 부분 문자열  (0) 2020.02.16

BOJ : https://www.acmicpc.net/problem/11403

github : https://github.com/junho0956/Algorithm/blob/master/11403/11403/%EC%86%8C%EC%8A%A4.cpp

 

문제는 DFS, BFS, FLOYD 3가지 알고리즘 중 1가지만 알고 계시면 해결가능합니다.

아래 코드는 DFS 로 구현한 코드입니다.

현재위치 [i,j] 가 1이면 i->j 가 가능한 것이므로 이에 대한 가능한 모든 정점을 방문하는 dfs를 구현하였습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
int arr[101][101];
int ans[101][101];
int N;
vector<int> v[101];
bool visit[101];
 
void dfs(int s, int e, int m) {
    visit[e] = true;
    ans[m][e] = 1;
 
    for (int i = 1; i <= N; i++) {
        if (arr[e][i] && !visit[i]) dfs(e, i, m);
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> arr[i][j];
            v[i].push_back(j);
        }
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (arr[i][j]) {
                memset(visit, 0, sizeof(visit));
                dfs(i, j, i);
            }
        }
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cout << ans[i][j] << ' ';
        }
        cout << "\n";
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 15988번 1, 2, 3 더하기 3  (0) 2020.02.18
BOJ 12101번 1, 2, 3 더하기2  (0) 2020.02.18
BOJ 11046번 팰린드롬??  (0) 2020.02.16
BOJ 13275번 가장 긴 팰린드롬 부분 문자열  (0) 2020.02.16
BOJ 10942번 팰린드롬?  (0) 2020.02.16

BOJ : https://www.acmicpc.net/problem/11046

github : https://github.com/junho0956/Algorithm/blob/master/11046/11046/%EC%86%8C%EC%8A%A4.cpp

 

팰린드롬? 과 같은문제인데

범위가 2000에서 백만으로 늘어나면서, 2차원 dp로는 TLE가 발생하는 문제이다.

manacher's algorithm을 통해서 문제를 해결해야한다.

 

단 펠린드롬? 문제처럼 스트링에 숫자+'0' 형식으로 제출했더니

계속 틀린다고 나오길래 아예 숫자형식으로만 사용해봤는데 바로 AC가 떳다.

 

팰린드롬? 문제와 입력되는 값의 범위는 10만이하로 같은데 무슨차이인지 모르겠다,,

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <algorithm>
using namespace std;
 
int dp[2000200];
int str[2000200];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    int N; cin >> N;
    int len = N * 2 - 1;
    for (int i = 0; i < len; i++) {
        int num; cin >> str[i++];
    }
 
    int r, p;
    r = p = 0;
    for (int i = 0; i < len; i++) {
        if (i <= r) dp[i] = min(r - i, dp[p * 2 - i]);
        else dp[i] = 0;
 
        while (i + dp[i] + 1 < len && i - dp[i] - 1 >= 0 && str[i + dp[i] + 1] == str[i - dp[i] - 1]) dp[i]++;
        if (i + dp[i] > r) {
            r = i + dp[i];
            p = i;
        }
    }
 
    int T; cin >> T;
    while (T--) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        a *= 2;
        b *= 2;
        int mid = (a + b) / 2;
        if (mid + dp[mid] >= b) cout << "1\n";
        else cout << "0\n";
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 12101번 1, 2, 3 더하기2  (0) 2020.02.18
BOJ 11403번 경로 찾기  (0) 2020.02.17
BOJ 13275번 가장 긴 팰린드롬 부분 문자열  (0) 2020.02.16
BOJ 10942번 팰린드롬?  (0) 2020.02.16
BOJ 1695번 팰린드롬 만들기  (0) 2020.02.16

BOJ : https://www.acmicpc.net/problem/13275

github : https://github.com/junho0956/Algorithm/blob/master/13275/13275/%EC%86%8C%EC%8A%A4.cpp

 

manacher's Algorithm 을 통하여 해결했습니다.

 

manacher's 알고리즘을 구현시 dp에는 인덱스 i 기준 팰린드롬을 만들 수 있는 범위가 설정됩니다.

이를 이용하면 가장 긴 팰린드롬 부분 문자열을 만들 수 있습니다.

단 짝수의 경우가 있으니 문자열 사이에 임의의 문자열을 삽입하여 홀수로 만들고 시작합니다.

 

dp를 갱신해가면서 그 범위를 max를 통해 저장해두고 마지막에 그 값에 대한 정답을 출력하면,

스트링의 첫 부분과 마지막 부분에 대한 반례가 생길 것 같았습니다.

그 이유는 짝수를 고려한 부분문자열을 추가했기 때문입니다.

 

그래서 현재 dp[i] 에 대해서 스트링 str의 값이 # 인지 아닌지로 먼저 구별하였고,

str[i+dp[i]] 가 # 인지 아닌지 재구별하였습니다.

만약 #이면 정확한 길이가 아니기 때문입니다.

그 후에는 dp[i]의 값이 짝수인지, 홀수인지에 따른 실제 길이를 계산해주었습니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
 
int dp[200010];
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    string a, str;
    int len;
 
    cin >> a;
    for (int i = 0; i < a.size(); i++) {
        str += a[i];
        str += '#';
    }
    str.pop_back();
 
    int r = 0, p = 0;
    len = str.size();
 
    for (int i = 0; i < len; i++) {
        if (i <= r) dp[i] = min(r - i, dp[p*2-i]);
        else dp[i] = 0;
        while (i + dp[i] + 1 < len && i - dp[i] - 1 >= 0 && str[i + dp[i] + 1] == str[i - dp[i] - 1]) dp[i]++;
        if (i + dp[i] > r) {
            r = i + dp[i];
            p = i;
        }
    }
 
    int ans = 0;
    for (int i = 0; i < len; i++) {
        if (dp[i]) {
            // even
            if (str[i] == '#') {
                int temp = dp[i];
                if (str[i + dp[i]] == '#') temp--;
                int cnt = (temp / 2 + 1) * 2;
                ans = max(ans, cnt);
            }
            // odd
            else {
                int temp = dp[i];
                if (str[i + dp[i]] == '#') temp--;
                int cnt = temp+1;
                ans = max(ans, cnt);
            }
        }
    }
    if (ans == 0) ans = 1;
    cout << ans;
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 11403번 경로 찾기  (0) 2020.02.17
BOJ 11046번 팰린드롬??  (0) 2020.02.16
BOJ 10942번 팰린드롬?  (0) 2020.02.16
BOJ 1695번 팰린드롬 만들기  (0) 2020.02.16
BOJ 1213번 팰린드롬 만들기  (0) 2020.02.16

+ Recent posts

티스토리툴바