[11985] 오렌지 출하
BOJ/DP2018. 6. 21. 01:18
### DP ###
[11985] 오렌지 출하 : http://boj.kr/11985
<소스코드>
d[i] : 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 | #include <stdio.h> int a[20001]; long long d[21001]; int n, m, k; long long min(long long a, long long b) { return a < b ? a : b; } long long orange(int s, int e) { long long *ret = &d[s]; int size, big=0, small=0x7fffffff; long long box; if(s >= e) return 0; if(*ret != -1) return *ret; *ret = 0x7fffffffffffffff; size = m < e-s+1 ? m : e-s+1; for(int i=0; i<size; i++) { if(big < a[s+i]) big = a[s+i]; if(small > a[s+i]) small = a[s+i]; box = 1LL*(i+1)*(big-small) + k; *ret = min(*ret, box+orange(s+i+1, e)); } return *ret; } int main() { scanf("%d%d%d", &n, &m, &k); for(int i=0; i<n; i++) { scanf("%d", a+i); d[i] = -1; } printf("%lld\n", orange(0, n)); return 0; } | cs |
>> 시간복잡도 : O(NM)
'BOJ > DP' 카테고리의 다른 글
| [9177] 단어 섞기 (0) | 2018.05.22 |
|---|---|
| [2602] 돌다리 건너기 (0) | 2018.05.17 |
| [9252] LCS2 (0) | 2018.04.22 |
| [9251] LCS (0) | 2018.04.21 |
| [14002] 가장 긴 증가하는 부분 수열 4 (0) | 2018.04.18 |
[9177] 단어 섞기
BOJ/DP2018. 5. 22. 10:58
[9177] 단어 섞기 : http://boj.kr/9177
### DP ###
d[i][j] : 문자열 a의 i번째, 문자열 b의 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 36 37 38 39 | #include <stdio.h> #include <string.h> int aLen, bLen; char a[201], b[201], c[401]; int d[201][201]; int word(int aIdx, int bIdx, int cIdx) { int *ret = &d[aIdx][bIdx]; if(aIdx == aLen && bIdx == bLen) return 1; if(*ret != -1) return *ret; *ret = 0; if(a[aIdx] == c[cIdx]) *ret = word(aIdx+1, bIdx, cIdx+1); if(*ret) return *ret; if(b[bIdx] == c[cIdx]) *ret = word(aIdx, bIdx+1, cIdx+1); return *ret; } int main() { int n; scanf("%d", &n); for(int tc=1; tc<=n; tc++) { scanf("%s%s%s", a, b, c); printf("Data set %d: ", tc); aLen = strlen(a); bLen = strlen(b); memset(d, -1, sizeof(d)); word(0, 0, 0) ? puts("yes") : puts("no"); } return 0; } | cs |
>> 처음에는 그리디방식으로 햇는데, 두번째 테케가 반례가 되어버렸다.
>> 유형이 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 | #include <stdio.h> #include <string.h> int aLen, bLen; char a[201], b[201], c[401]; int d[201][201][401]; int word(int aIdx, int bIdx, int cIdx) { int *ret = &d[aIdx][bIdx][cIdx]; if(aIdx == aLen && bIdx == bLen) return 1; if(*ret != -1) return *ret; *ret = 0; if(a[aIdx] == c[cIdx]) *ret = word(aIdx+1, bIdx, cIdx+1); if(*ret) return *ret; if(b[bIdx] == c[cIdx]) *ret = word(aIdx, bIdx+1, cIdx+1); return *ret; } int main() { int n; scanf("%d", &n); for(int tc=1; tc<=n; tc++) { int ai=0, bi=0, ci=0; scanf("%s%s%s", a, b, c); printf("Data set %d: ", tc); aLen = strlen(a); bLen = strlen(b); memset(d, -1, sizeof(d)); word(0, 0, 0) ? puts("yes") : puts("no"); } return 0; } | cs |
>> AC 받은 코드와 차이가 있다면 cache 역할을 하는 배열을 3차원으로 잡은것. 생각해보면 2차원으로 충분하단 생각이 들었다.
>> 그리고 시간초과 난 이유를 곰곰히 생각해보니, 매 테케마다(n*200*200*400에 해당하는) memset() 을 돌려 그런 것 같아.
'BOJ > DP' 카테고리의 다른 글
| [11985] 오렌지 출하 (0) | 2018.06.21 |
|---|---|
| [2602] 돌다리 건너기 (0) | 2018.05.17 |
| [9252] LCS2 (0) | 2018.04.22 |
| [9251] LCS (0) | 2018.04.21 |
| [14002] 가장 긴 증가하는 부분 수열 4 (0) | 2018.04.18 |
[2602] 돌다리 건너기
BOJ/DP2018. 5. 17. 00:25
[2602] 돌다리 건너기 : http://boj.kr/2602
- 난 3차원으로 풀었는데, 다른 사람들은 2차원으로 풀었다.
d[bidx][ad][sidx] : 상태가 ad(0은 천사차례, 1은 악마차례) 일때,
bidx번째 돌다리에서, sidx 번째 문자부터 시작하는 문자열에 적힌 순서대로 다리를 건널 수 있는 방법의 수
<소스코드>
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> char str[21]; char ang[101], dev[101]; int d[101][2][21]; int bridge(int bidx, int ad, int sidx) { int *ret = &d[bidx][ad][sidx]; if(!str[sidx]) return 1; if(ad == 0 && !ang[bidx]) return 0; if(ad == 1 && !dev[bidx]) return 0; if(*ret) return *ret; if(ad == 0) { if(ang[bidx] == str[sidx]) *ret = bridge(bidx+1, !ad, sidx+1); *ret += bridge(bidx+1, ad, sidx); } else { if(dev[bidx] == str[sidx]) *ret = bridge(bidx+1, !ad, sidx+1); *ret += bridge(bidx+1, ad, sidx); } return *ret; } int main() { scanf("%s%s%s", str, ang, dev); printf("%d\n", bridge(0, 0, 0)+bridge(0, 1, 0)); return 0; } | cs |
>> 천사다리를 먼저 택한 경우 + 악마다리를 먼저 택한 경우
'BOJ > DP' 카테고리의 다른 글
| [11985] 오렌지 출하 (0) | 2018.06.21 |
|---|---|
| [9177] 단어 섞기 (0) | 2018.05.22 |
| [9252] LCS2 (0) | 2018.04.22 |
| [9251] LCS (0) | 2018.04.21 |
| [14002] 가장 긴 증가하는 부분 수열 4 (0) | 2018.04.18 |
[9252] LCS2
BOJ/DP2018. 4. 22. 02:07
[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
BOJ/DP2018. 4. 21. 02:14
[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
BOJ/DP2018. 4. 18. 18:36
[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 |
[10942] 팰린드롬?
BOJ/DP2018. 2. 22. 23:49
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] 문자열과 점수
BOJ/DP2018. 2. 21. 08:15
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
>> 정답코드에서는 -6이, 위 코드에서는 -4가 나온다...
'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] 이동하기
BOJ/DP2018. 2. 18. 01:24
기본 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 |
