[9252] LCS2
[9252] LCS2 : http://boj.kr/9252
### DP -Track ### (참고 : https://kks227.blog.me/221028710658)
< 소스코드 >
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 <cstdio> #include <cstring> #include <stack> using namespace std; struct P { int ret, si; }; char s[1001], t[1001]; int d[1001][1001]; char a[1001]; stack<P> st; int max(int a, int b) { return a > b ? a : b; } int lcs2(int si, int ti) { int ret = 0; if(si < 0 || ti < 0) return 0; if(d[si][ti] != -1) return d[si][ti]; if(s[si] == t[ti]) { ret = lcs2(si-1, ti-1)+1; st.push((P){ret, si}); } else { ret = max(lcs2(si-1, ti), lcs2(si, ti-1)); } return d[si][ti] = ret; } int main() { int sLen=0, tLen=0; scanf("%s%s", s, t); while(s[sLen]) sLen++; while(t[tLen]) tLen++; memset(d, -1, sizeof(d)); int ans = lcs2(sLen-1, tLen-1); printf("%d\n", ans); while(!st.empty()) { if(st.top().ret == ans) { a[--ans] = s[st.top().si]; } st.pop(); } puts(a); } | cs |
>> 아이디어는 부분문제의 답을 통해 역으로 그 답을 끼워 맞춘다.
>> 테스트 케이스는 아래와 같다.
ACAYKP
CAPCAK
>> 위 테케에 대한 아웃풋은 아래와 같다.
4
ACAK
>> 위 코드의 경우, 스택 st의 ret 에는 3 4 2 1 3 2 1 가 저장이 된다.
>> 맨 처음 정답에 해당하는 4일때의 si, 그다음 작은 숫자인 3일때의 si, ...
>> 이렇게 문자를 거꾸로 저장한 다음 출력하면 답이 된다.
'BOJ > DP' 카테고리의 다른 글
[9177] 단어 섞기 (0) | 2018.05.22 |
---|---|
[2602] 돌다리 건너기 (0) | 2018.05.17 |
[9251] LCS (0) | 2018.04.21 |
[14002] 가장 긴 증가하는 부분 수열 4 (0) | 2018.04.18 |
[10942] 팰린드롬? (0) | 2018.02.22 |
[9251] LCS
[9251] LSC : http://boj.kr/9251
### DP ###
lcs(si, ti) : 문자열 s의 si번째 문자까지, t의 ti번째의 문자까지의 가장 긴 증가하는 부분 문자열 (최장 공통 부분 수열)
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 | #include <stdio.h> #include <string.h> char s[1001], t[1001]; int d[1001][1001]; int max(int a, int b) { return a > b ? a : b; } int lcs(int si, int ti) { int ret = 0; if(si < 0 || ti < 0) return 0; if(d[si][ti] != -1) return d[si][ti]; if(s[si] == t[ti]) { ret = lcs(si-1, ti-1)+1; } else { ret = max(lcs(si-1, ti), lcs(si, ti-1)); } return d[si][ti] = ret; } int main() { int sLen=0, tLen=0; scanf("%s%s", s, t); while(s[sLen]) sLen++; while(t[tLen]) tLen++; memset(d, -1, sizeof(d)); printf("%d\n", lcs(sLen-1, tLen-1)); return 0; } | cs |
'BOJ > DP' 카테고리의 다른 글
[2602] 돌다리 건너기 (0) | 2018.05.17 |
---|---|
[9252] LCS2 (0) | 2018.04.22 |
[14002] 가장 긴 증가하는 부분 수열 4 (0) | 2018.04.18 |
[10942] 팰린드롬? (0) | 2018.02.22 |
[1890] 점프 (0) | 2018.02.22 |
[14002] 가장 긴 증가하는 부분 수열 4
[14002] 가장 긴 증가하는 부분 수열 4 : http://boj.kr/14002
< 소스코드 >
lis(s) : s 번째에서 시작하는 가장 긴 증가하는 부분 수열
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 57 58 | #include <stdio.h> #include <string.h> int n; int a[1001], d[1001]; int next[1001]; int lis(int s) { int ret=0; if(d[s]) return d[s]; for(int i=s+1; i<n; i++) { if(a[s] < a[i]) { int cur = lis(i); if(ret < cur) { ret = cur; next[s] = i; } } } return d[s] = ret+1; } void path(int k) { if(k == -1) return ; printf("%d ", a[k]); path(next[k]); } int main() { int k, ans=0; scanf("%d", &n); for(int i=0; i<n; i++) scanf("%d", a+i); memset(next, -1, sizeof(next)); for(int i=0; i<n; i++) { int tmp = lis(i); if(ans < tmp) { ans = tmp; k = i; } } printf("%d\n", ans); path(k); puts(""); return 0; } | cs |
>> next[i] 는 i의 다음 수열에 해당하는 인덱스.
>> n 제한이 1000 이라, O(n^2) 인 재귀로 가능하다.
'BOJ > DP' 카테고리의 다른 글
[9252] LCS2 (0) | 2018.04.22 |
---|---|
[9251] LCS (0) | 2018.04.21 |
[10942] 팰린드롬? (0) | 2018.02.22 |
[1890] 점프 (0) | 2018.02.22 |
[2216] 문자열과 점수 (0) | 2018.02.21 |
[14890] 경사로
[14890] 경사로 (http://boj.kr/14890)
right() 에서 L = 2 인경우
3 2 2 2 3
3 2 2 1 1
x x 3 2 2 (마지막 위치)
2 2 3
3 3 3
위 경우에 대해서 잘 처리해주면 된다. down() 도 마찬가지.
< 소스코드 >
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 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 | #include <stdio.h> int N, L, ans=0; int g[101][101]; int down(int r, int c) { int curH; if(r == N-1) return 1; curH = g[r][c]; if(r+L < N && curH-g[r+L][c] == 1) { int flag = 1; for(int i=1; i<L; i++) { if(g[r+L][c] != g[r+i][c]) flag = 0; } if(flag){ if(r+L == N-1) return 1; if(g[r+L][c] == g[r+L+1][c]) return down(r+L+1, c); if(g[r+L][c] == g[r+L+1][c]+1) return down(r+L, c); } } if(r+L < N && g[r+L][c]-curH == 1) { int flag = 1; for(int i=1; i<L; i++) { if(curH != g[r+i][c]) flag = 0; } if(flag) return down(r+L, c); } if(g[r+1][c] == curH) return down(r+1, c); return 0; } int right(int r, int c) { int curH; if(c == N-1) return 1; curH = g[r][c]; if(c+L < N && g[r][c+L]-curH == 1) { int flag = 1; for(int i=1; i<L; i++) { if(curH != g[r][c+i]) flag = 0; } if(flag) return right(r, c+L); } if(c+L < N && curH-g[r][c+L] == 1) { int flag = 1; for(int i=1; i<L; i++) { if(g[r][c+L] != g[r][c+i]) flag = 0; } if(flag) { if(c+L == N-1) return 1; if(g[r][c+L] == g[r][c+L+1]) return right(r, c+L+1); if(g[r][c+L] == g[r][c+L+1]+1) return right(r, c+L); } } if(g[r][c+1] == curH) return right(r, c+1); return 0; } int main() { scanf("%d%d", &N, &L); for(int i=0; i<N; i++) for(int j=0; j<N; j++) scanf("%d", &g[i][j]); for(int i=0; i<N; i++) { if(down(0, i)) ans++; if(right(i, 0)) ans++; } printf("%d\n", ans); return 0; } | cs |
>> 깔끔하게 경우의 수를 펜으로 써가며 확인했으면 금방 했을텐데, 괜히 머릿속으로 한다고 하다가, 시간만 많이 썼다...
'BOJ > SWEA' 카테고리의 다른 글
[14889] 스타트와 링크 (0) | 2018.02.28 |
---|---|
[14888] 연산자 끼워넣기 (0) | 2018.02.27 |
[14889] 스타트와 링크
- [14889] 스타트와 링크 (http://boj.kr/14889)
<소스코드>
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 57 58 59 60 | #include <stdio.h> int n, ans=1e9; int g[21][21]; int start[11], link[11]; int min(int a, int b) { return a < b ? a : b; } int abs(int k) { return k > 0 ? k : -k; } void go(int k, int ti, int ki) { if(ti == n/2 || ki == n/2) { int S=0, L=0; if(ti == n/2) { while(k) link[ki++] = k--; } if(ki == n/2) { while(k) start[ti++] = k--; } for(int i=0; i<ki; i++) { for(int j=i+1; j<ki; j++) { S += (g[start[i]][start[j]] + g[start[j]][start[i]]); L += (g[link[i]][link[j]] + g[link[j]][link[i]]); } } ans = min(ans, abs(S-L)); return ; } start[ti] = k; go(k-1, ti+1, ki); link[ki] = k; go(k-1, ti, ki+1); } int main() { int i, j; scanf("%d", &n); for(i=1; i<=n; i++) for(j=1; j<=n; j++) scanf("%d", &g[i][j]); go(n, 0, 0); printf("%d\n", ans); return 0; } | cs |
>> 한명씩 스타트에 넣고, 링크에 넣다가 둘중에 한 팀이 절반이 차면 나며지를 다른 팀에 마저 채운다. 그리고 계산!!
'BOJ > SWEA' 카테고리의 다른 글
[14890] 경사로 (0) | 2018.03.06 |
---|---|
[14888] 연산자 끼워넣기 (0) | 2018.02.27 |
[14888] 연산자 끼워넣기
[14888] 연산자 끼워넣기 (http://boj.kr/14888)
1) Brute Force 풀이
< 소스코드 >
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 | #include <stdio.h> int a[15], op[4]; int ansN = 1e9; int ansX = -1e9; int set[15]; void go(int n, int ps, int mi, int mu, int dv) { if(n == 1) { int ans = a[1]; for(int i=2; set[i]; i++) { if(set[i] == 1) ans += a[i]; else if(set[i] == 2) ans -= a[i]; else if(set[i] == 3) ans *= a[i]; else { if(ans < 0) { ans *= -1; ans /= a[i]; ans *= -1; } else ans /= a[i]; } } if(ans > ansX) ansX = ans; if(ans < ansN) ansN = ans; } if(ps) { set[n]=1; go(n-1, ps-1, mi, mu, dv); } if(mi) { set[n]=2; go(n-1, ps, mi-1, mu, dv); } if(mu) { set[n]=3; go(n-1, ps, mi, mu-1, dv); } if(dv) { set[n]=4; go(n-1, ps, mi, mu, dv-1); } } int main() { int n; scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d", a+i); for(int i=0; i<4; i++) scanf("%d", op+i); go(n, op[0], op[1], op[2], op[3]); printf("%d\n%d\n", ansX, ansN); return 0; } | cs |
>> 연산자 순서의 모든 경우의 수를 저장해 놓고, 그 순서에 맞게 계산을 한 다음 최대값과 최소값을 구한다.
2) DP 풀이
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 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 | #include <stdio.h> int a[15], op[4]; int d[15][15][15][15][15]; int e[15][15][15][15][15]; const int INF=1e9; int max(int a, int b) { return a > b ? a : b; } int min(int a, int b) { return a < b ? a : b; } int maxV(int n, int ps, int mi, int mu, int dv) { int ans = -INF; if(n == 1) return a[n]; if(d[n][ps][mi][mu][dv]!=INF+1) return d[n][ps][mi][mu][dv]; if(ps) ans = max(ans, maxV(n-1, ps-1, mi, mu, dv)+a[n]); if(mi) ans = max(ans, maxV(n-1, ps, mi-1, mu, dv)-a[n]); if(mu) ans = max(ans, maxV(n-1, ps, mi, mu-1, dv)*a[n]); if(dv) { int tmp = maxV(n-1, ps, mi, mu, dv-1); if(tmp < 0) { tmp *= -1; tmp /= a[n]; tmp *= -1; } else tmp /= a[n]; ans = max(ans, tmp); } return d[n][ps][mi][mu][dv] = ans; } int minV(int n, int ps, int mi, int mu, int dv) { int ans = INF; if(n == 1) return a[n]; if(e[n][ps][mi][mu][dv]!=INF+1) return e[n][ps][mi][mu][dv]; if(ps) ans = min(ans, minV(n-1, ps-1, mi, mu, dv)+a[n]); if(mi) ans = min(ans, minV(n-1, ps, mi-1, mu, dv)-a[n]); if(mu) ans = min(ans, minV(n-1, ps, mi, mu-1, dv)*a[n]); if(dv) { int tmp = minV(n-1, ps, mi, mu, dv-1); if(tmp < 0) { tmp *= -1; tmp /= a[n]; tmp *= -1; } else tmp /= a[n]; ans = min(ans, tmp); } return e[n][ps][mi][mu][dv] = ans; } int main() { int n; scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d", a+i); for(int i=0; i<4; i++) scanf("%d", op+i); for(int i=0; i<15; i++) for(int j=0; j<15; j++) for(int k=0; k<15; k++) for(int l=0; l<15; l++) for(int m=0; m<15; m++) d[i][j][k][l][m] = e[i][j][k][l][m] = INF+1; printf("%d\n", maxV(n, op[0], op[1], op[2], op[3])); printf("%d\n", minV(n, op[0], op[1], op[2], op[3])); return 0; } | cs |
>> 맨처음 풀이에 대해 잘못된 점을 파악한 다음(나눗셈에 대한 처리), 코드를 수정하니 AC 를 받았다.
>> 근데 다시생각해보면 왜 DP 로 가능한지 모르겠다...
< 마지막 테케가 안나오는 소스코드 >
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 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 | #include <stdio.h> int a[15], op[4]; int d[15][15][15][15][15]; int e[15][15][15][15][15]; const int INF=1e9; int max(int a, int b) { return a > b ? a : b; } int min(int a, int b) { return a < b ? a : b; } int maxV(int n, int ps, int mi, int mu, int dv) { int ans = -INF; if(n == 1) return a[n]; if(d[n][ps][mi][mu][dv]!=INF+1) return d[n][ps][mi][mu][dv]; if(ps) ans = max(ans, maxV(n-1, ps-1, mi, mu, dv)+a[n]); if(mi) ans = max(ans, maxV(n-1, ps, mi-1, mu, dv)-a[n]); if(mu) ans = max(ans, maxV(n-1, ps, mi, mu-1, dv)*a[n]); if(dv) { int tmp = maxV(n-1, ps, mi, mu, dv-1); if(tmp < 0) tmp *= -1; tmp /= a[n]; tmp *= -1; ans = max(ans, tmp); } return d[n][ps][mi][mu][dv] = ans; } int minV(int n, int ps, int mi, int mu, int dv) { int ans = INF; if(n == 1) return a[n]; if(e[n][ps][mi][mu][dv]!=INF+1) return e[n][ps][mi][mu][dv]; if(ps) ans = min(ans, minV(n-1, ps-1, mi, mu, dv)+a[n]); if(mi) ans = min(ans, minV(n-1, ps, mi-1, mu, dv)-a[n]); if(mu) ans = min(ans, minV(n-1, ps, mi, mu-1, dv)*a[n]); if(dv) { int tmp = minV(n-1, ps, mi, mu, dv-1); if(tmp < 0) tmp *= -1; tmp /= a[n]; tmp *= -1; ans = min(ans, tmp); } return e[n][ps][mi][mu][dv] = ans; } int main() { int n; scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d", a+i); for(int i=0; i<4; i++) scanf("%d", op+i); for(int i=0; i<15; i++) for(int j=0; j<15; j++) for(int k=0; k<15; k++) for(int l=0; l<15; l++) for(int m=0; m<15; m++) d[i][j][k][l][m] = e[i][j][k][l][m] = INF+1; printf("%d\n", maxV(n, op[0], op[1], op[2], op[3])); printf("%d\n", minV(n, op[0], op[1], op[2], op[3])); return 0; } | cs |
>> 마지막 테케의 최소값이 -36이 나온다..... -24 라는데...ㅜ
>> 가만 생각해보니 DP 가 아닌 것 같다. 모든 경우의 수를 생각해서 풀면 될 것 같은 생각이 든다. (brute force)
>> 나눗셈에 대한 처리를 잘못했다.
'BOJ > SWEA' 카테고리의 다른 글
[14890] 경사로 (0) | 2018.03.06 |
---|---|
[14889] 스타트와 링크 (0) | 2018.02.28 |
[10942] 팰린드롬?
DP - basic
d[i][j] = i~j 까지가 팰린드롬인지.
< 소스코드 >
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 | #include <stdio.h> #include <string.h> int p[2001]; int d[2001][2001]; int isP(int s, int e) { int i; if(s >= e) return 1; if(d[s][e] != -1) return d[s][e]; if(p[s] != p[e]) return 0; return d[s][e] = isP(s+1, e-1); } int main() { int i, j, n, m; scanf("%d", &n); for(i=1; i<=n; i++) scanf("%d", p+i); memset(d, -1, sizeof(d)); scanf("%d", &m); while(m--) { int a, b; scanf("%d%d", &a, &b); printf("%d\n", isP(a, b)); } return 0; } | cs |
>> 모든 경우를 다 구해놓고 하려다가 시간만 쓰고, 머리만 쓴거 같다.
>> 쿼리마다 필요한걸 구하면서 그때 구한걸 저장해(메모이제이션) 놓으면 된다..
< 바텀업 >
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 | #include <cstdio> int n; int a[2000]; bool d[2000][2000]; int main() { scanf("%d",&n); for (int i=0; i<n; i++) { scanf("%d",&a[i]); } for (int i=0; i<n; i++) { d[i][i] = true; } for (int i=0; i<n-1; i++) { if (a[i] == a[i+1]) { d[i][i+1] = true; } } for (int k=3; k<=n; k++) { for (int i=0; i<=n-k; i++) { int j = i+k-1; if (a[i] == a[j] && d[i+1][j-1]) { d[i][j] = true; } } } int m; scanf("%d",&m); while (m--) { int s, e; scanf("%d %d",&s,&e); printf("%d\n",d[s-1][e-1]); } return 0; } | cs |
>> 과거 AC 받은 코드인데, 백준님 코드 같다.. 내스타일의 코드는 아니므로...
>> 길이가 1인 부분수열은 반드시 팰린드롬이다.
>> 길이가 2인 부분수열은 두 수가 같을때만 팰린드롬이다.
>> d[i][j] 가 팰린드롬이려면 a[i] == a[j] 이고 d[i+1][j-1] 이 팰린드롬이여야 한다.
'BOJ > DP' 카테고리의 다른 글
[9251] LCS (0) | 2018.04.21 |
---|---|
[14002] 가장 긴 증가하는 부분 수열 4 (0) | 2018.04.18 |
[1890] 점프 (0) | 2018.02.22 |
[2216] 문자열과 점수 (0) | 2018.02.21 |
[11048] 이동하기 (0) | 2018.02.18 |
DP - basic
D[i][j] : (1, 1)에서 (i, j) 까지 오는 방법의 수
< 소스코드 >
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 | #include <stdio.h> int n; int g[101][101]; long long d[101][101]; long long jump(int r, int c) { int k = g[r][c]; long long ret = 0; if(r == n && c == n) return 1; if(r > n || c > n || k == 0) return 0; if(d[r][c] != -1) return d[r][c]; ret += jump(r+k, c); ret += jump(r, c+k); return d[r][c] = ret; } int main() { int i, j; scanf("%d", &n); for(i=1; i<=n; i++) { for(j=1; j<=n; j++) { scanf("%d", &g[i][j]); d[i][j] = 1LL*(-1); } } printf("%lld\n", jump(1, 1)); return 0; } | cs |
>> 10 : ret 를 int 로 선언해서 81%에서 틀렸었다....
< 과거 소스코드 >
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 | #include <stdio.h> int g[101][101]; long long d[101][101]; long long go(int i, int j) { int k; if(i<1 || j<1) return 0; if(i==1 && j==1) return 1; if(d[i][j]) return d[i][j]; for(k=0; k<j; k++) if(k+g[i][k] == j) d[i][j] += go(i, k); for(k=0; k<i; k++) if(k+g[k][j] == i) d[i][j] += go(k, j); return d[i][j]; } int main() { int n, i, j; scanf("%d", &n); for(i=1; i<=n; i++) for(j=1; j<=n; j++) scanf("%d", &g[i][j]); printf("%lld\n", go(n, n));; return 0; } | cs |
>> 역시 재귀로 풀었지만, go(n, n) 으로 시작해서 불필요하게 머리를 더 쓴거 같다..
'BOJ > DP' 카테고리의 다른 글
[14002] 가장 긴 증가하는 부분 수열 4 (0) | 2018.04.18 |
---|---|
[10942] 팰린드롬? (0) | 2018.02.22 |
[2216] 문자열과 점수 (0) | 2018.02.21 |
[11048] 이동하기 (0) | 2018.02.18 |
[9184] 신나는 함수 실행 (0) | 2018.02.16 |
[2216] 문자열과 점수
d[i][j] = s의 i번째 문자열까지, t의 j번째 문자열까지의 최대 점수
< AC 코드 >
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 | #include <stdio.h> #include <string.h> #define mINF 0x80000000 int a, b, c; int slen, tlen; char s[3005], t[3005]; int d[3005][3005]; int max(int x, int y) { return x > y ? x : y; } int go(int si, int ti) { int ret = mINF; if(d[si][ti]!=mINF) return d[si][ti]; if(si == slen) return b * (tlen-ti); if(ti == tlen) return b * (slen-si); if(s[si] == t[ti]) ret = max(ret, go(si+1, ti+1)+a); if(s[si] != t[ti]) ret = max(ret, go(si+1, ti+1)+c); ret = max(ret, go(si+1, ti)+b); ret = max(ret, go(si, ti+1)+b); return d[si][ti] = ret; } int main() { int i, j; scanf("%d%d%d%s%s", &a, &b, &c, s, t); slen = strlen(s); tlen = strlen(t); for(i=0; i<3005; i++) for(j=0; j<3005; j++) d[i][j] = mINF; printf("%d\n", go(0, 0)); return 0; } | cs |
>> 0x8000000 : int 의 최소값이다.
>> 무조건 위에서 아래로 가도록 짜진 말아야겠다...
< 틀린 코드 >
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 | #include <stdio.h> #include <string.h> #define mINF 0x80000000 int a, b, c; char s[3005], t[3005]; int d[3005][3005]; int max(int x, int y) { return x > y ? x : y; } int go(int si, int ti) { int ret = mINF; if(si < 0) return b * (ti-1); if(ti < 0) return b * (si-1); if(d[si][ti]!=mINF) return d[si][ti]; if(s[si] == t[ti]) ret = max(ret, go(si-1, ti-1)+a); if(s[si] != t[ti]) ret = max(ret, go(si-1, ti-1)+c); ret = max(ret, go(si-1, ti)+b); ret = max(ret, go(si, ti-1)+b); return d[si][ti] = ret; } int main() { int i, j; scanf("%d%d%d%s%s", &a, &b, &c, s, t); for(i=0; i<3005; i++) for(j=0; j<3005; j++) d[i][j] = mINF; printf("%d\n", go(strlen(s)-1, strlen(t))-1); return 0; } | cs |
>> 점화식은 맞는데, 18%에서 틀렸다고 한다. 왜 틀린건지 모르겠다...ㅜㅜ
>> 17, 18 에서의 탈출조건도 ti+1, si+1 인거 같은데, 이렇게 하면 테케도 통과를 못한다...
>> 위 코드에 대한 반례
5 -3 -6
a
b
'BOJ > DP' 카테고리의 다른 글
[10942] 팰린드롬? (0) | 2018.02.22 |
---|---|
[1890] 점프 (0) | 2018.02.22 |
[11048] 이동하기 (0) | 2018.02.18 |
[9184] 신나는 함수 실행 (0) | 2018.02.16 |
[2302] 극장 좌석 (0) | 2018.02.05 |
[11048] 이동하기
기본 DP2.
D[i][j] : (1, 1) 에서 (i, j)으로 이동하면서 가져올 수 있는 사탕의 최대 갯수
< 소스코드 >
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 | #include <stdio.h> int g[1001][1001]; int d[1001][1001]; int go(int n, int m) { int a, b; if(!n || !m) return 0; if(d[n][m] != -1) return d[n][m]; a = go(n-1, m); b = go(n, m-1); return d[n][m] = (a > b ? a : b) + g[n][m]; } int main() { int i, j; int n, m; scanf("%d%d", &n, &m); for(i=1; i<=n; i++) { for(j=1; j<=m; j++) { scanf("%d", &g[i][j]); d[i][j] = -1; } } printf("%d\n", go(n, m)); return 0; } | cs |
>> go(n-1, m-1) 은 고려할 필요가 없다.
< Bottom Up >
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | #include <stdio.h> int n, m, g[1001][1001], d[1001][1001]; int main() { int i, j, tmp; scanf("%d %d", &n, &m); for(i=1; i<=n; i++) for(j=1; j<=m; j++) scanf("%d", &g[i][j]); for(i=1; i<=n; i++) { for(j=1; j<=m; j++) { d[i][j] = g[i][j]; tmp = d[i-1][j] > d[i][j-1] ? d[i-1][j] : d[i][j-1]; d[i][j] += tmp; } } printf("%d\n", d[n][m]); return 0; } | cs |
'BOJ > DP' 카테고리의 다른 글
[1890] 점프 (0) | 2018.02.22 |
---|---|
[2216] 문자열과 점수 (0) | 2018.02.21 |
[9184] 신나는 함수 실행 (0) | 2018.02.16 |
[2302] 극장 좌석 (0) | 2018.02.05 |
[1937] 욕심쟁이 판다 (0) | 2018.02.01 |