[9184] 신나는 함수 실행
- 메모이제이션만 하면 된다.
< 소스코드 >
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 | #include <stdio.h> int d[21][21][21]; int w(int a, int b, int c) { if(a <= 0 || b <= 0 || c <= 0) return 1; if(a > 20 || b > 20 || c > 20) return w(20, 20, 20); if(d[a][b][c]) return d[a][b][c]; if(a < b && b < c) return d[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c); return d[a][b][c] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1); } int main() { while(1) { int a, b, c; scanf("%d%d%d", &a, &b, &c); if(a == -1 && b == -1 && c == -1) break; printf("w(%d, %d, %d) = %d\n", a, b, c, w(a, b, c)); } return 0; } | cs |
>> 12 라인을 9번 라인보다 먼저 써서 런타임에러가 발생했었다...
>> 배열의 각 차원의 크기는 21인데, a, b, c 중 20보다 큰 값이 들어오면 저 코드를 먼저 실행하게
되어 런타임 에러가 발생하는 듯 하다.
'BOJ > DP' 카테고리의 다른 글
[2216] 문자열과 점수 (0) | 2018.02.21 |
---|---|
[11048] 이동하기 (0) | 2018.02.18 |
[2302] 극장 좌석 (0) | 2018.02.05 |
[1937] 욕심쟁이 판다 (0) | 2018.02.01 |
[1309] 동물원 (0) | 2018.02.01 |
[2302] 극장 좌석
d[n] : VIP 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수
- 소스코드
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 | #include <stdio.h> int vip[41], d[41]; int go(int k) { int ret; if(k == 0 || k == 1) return 1; if(d[k]) return d[k]; if(vip[k]) return d[k] = go(k-1); ret = go(k-1); if(!vip[k-1]) ret += go(k-2); return d[k] = ret; } int main() { int n, m, k; scanf("%d%d", &n, &m); while(m--) { scanf("%d", &k); vip[k] = 1; } printf("%d\n", go(n)); return 0; } | cs |
>> n이 n번에 앉았을 때의 경우의 수 : d[n-1]
>> n이 n-1에 앉았을 때의 경우의 수 : d[n-2]
>> 여기서는 10번 라인을 쓰지 않으면, n-1번이 vip석이 아닌경우 n번이 vip석이여도 n-1과 n번이
바꿔 앉는 경우를 세어 중복이 발생한다.
'BOJ > DP' 카테고리의 다른 글
[11048] 이동하기 (0) | 2018.02.18 |
---|---|
[9184] 신나는 함수 실행 (0) | 2018.02.16 |
[1937] 욕심쟁이 판다 (0) | 2018.02.01 |
[1309] 동물원 (0) | 2018.02.01 |
[1932] 숫자삼각형 (0) | 2018.02.01 |
[1937] 욕심쟁이 판다
d[r][c] : (r, c)에서 대나무를 먹기 시작했을 때, 판다가 살 수 있는 최대 일수.
- 소스코드
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 n; int g[505][505]; int d[505][505]; int dr[]={1, 0, -1, 0}; int dc[]={0, 1, 0, -1}; int max(int a, int b) { return a > b ? a : b; } int go(int r, int c) { int i, ret=1; if(d[r][c]) return d[r][c]; for(i=0; i<4; i++) { int nr = r+dr[i]; int nc = c+dc[i]; if(g[r][c] < g[nr][nc]) { ret = max(ret, go(nr, nc)+1); } } return d[r][c] = ret; } int main() { int i, j, ans = 0; scanf("%d", &n); for(i=1; i<=n; i++) for(j=1; j<=n; j++) scanf("%d", &g[i][j]); for(i=1; i<=n; i++) for(j=1; j<=n; j++) ans = max(ans, go(i, j)); printf("%d\n", ans); return 0; } | cs |
>> 오타때문에 두번 틀렸다...ㅜㅜ
>> 좌표를 (1,1) 부터 시작하고 사이즈를 505로 넉넉하게 잡으면, 좌표를 벗어날 일이 없다.
'BOJ > DP' 카테고리의 다른 글
[9184] 신나는 함수 실행 (0) | 2018.02.16 |
---|---|
[2302] 극장 좌석 (0) | 2018.02.05 |
[1309] 동물원 (0) | 2018.02.01 |
[1932] 숫자삼각형 (0) | 2018.02.01 |
[1149] RGB 거리 (0) | 2018.01.30 |
[1309] 동물원
d[n][k] : n번째 줄에 상태가 k일 때, n번째 줄까지 사자를 배치할 수 있는 경우의 수
- 소스코드
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 | #include <stdio.h> #define MOD 9901 int d[100001][3]; int go(int n, int k) { int a, b; if(n == 0) return 1; if(d[n][k]) return d[n][k]; a = go(n-1, (k+1)%3); b = go(n-1, (k+2)%3); if(k == 0) a += go(n-1, 0); return d[n][k] = (a+b)%MOD; } int main() { int n; scanf("%d", &n); printf("%d\n", go(n, 0)); return 0; } | cs |
>> k = 0 인 경우는 둘 다 비워있는 상태.
>> k = 1 인 경우는 사자를 왼쪽에 배치, k = 2 인 경우는 사자를 오른쪽에 배치한 상태
'BOJ > DP' 카테고리의 다른 글
[2302] 극장 좌석 (0) | 2018.02.05 |
---|---|
[1937] 욕심쟁이 판다 (0) | 2018.02.01 |
[1932] 숫자삼각형 (0) | 2018.02.01 |
[1149] RGB 거리 (0) | 2018.01.30 |
[1463] 1로 만들기 (0) | 2018.01.26 |
[1932] 숫자삼각형
d[n][k] : n번째 줄의 k번째 숫자를 선택 했을 때,
1층부터 n층까지 아래로 내려오면서 더한 합의 최대값.
- 소스코드
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 | #include <stdio.h> #include <string.h> int g[505][505]; int d[505][505]; int max(int a, int b) { return a > b ? a : b; } int go(int n, int k) { int L, R; if(n == 0 || k == 0) return 0; if(d[n][k] != -1) return d[n][k]; L = go(n-1, k-1); R = go(n-1, k); return d[n][k] = g[n][k] + max(L, R); } int main() { int i, j, n; int ans=0; scanf("%d", &n); for(i=1; i<=n; i++) for(j=1; j<=i; j++) scanf("%d", &g[i][j]); memset(d, -1, sizeof(d)); for(i=1; i<=n; i++) ans = max(ans, go(n, i)); printf("%d\n", ans); return 0; } | cs |
>> 위의 줄 오른쪽 대각선의 k값은 현재 줄의 k값과 동일하며,
>> 위의 줄 왼쪽 대각선의 k값은 현재 줄의 k-1값과 동일.
>> k는 1부터 시작, g[n][0] = 0 인점을 이용.
- 아래 코드는 바텀업
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 | #include <stdio.h> int n, g[501][501], d[501][501]; int main() { int i, j, ans; scanf("%d", &n); for(i=1; i<=n; i++) for(j=1; j<=i; j++) scanf("%d", &g[i][j]); d[1][1] = g[1][1]; for(i=2; i<=n; i++) { for(j=1; j<=i; j++) { d[i][j] = d[i-1][j-1] > d[i-1][j] ? d[i-1][j-1] : d[i-1][j]; d[i][j] += g[i][j]; } } ans = d[n][1]; for(i=2; i<=n; i++) if(ans < d[n][i]) ans = d[n][i]; printf("%d\n", ans); return 0; } | cs |
>> 1년전에 푼 코드이고, 분명 직접 생각해내서 푼 기억은 있다.
>> 근데 보통 DP를 풀때 대부분의 문제를 탑다운으로 푸는데,,, 바텀업으로 풀려있다.
>> 코드의 원리는 위에서 설명한 아이디어와 동일하다.
'BOJ > DP' 카테고리의 다른 글
[2302] 극장 좌석 (0) | 2018.02.05 |
---|---|
[1937] 욕심쟁이 판다 (0) | 2018.02.01 |
[1309] 동물원 (0) | 2018.02.01 |
[1149] RGB 거리 (0) | 2018.01.30 |
[1463] 1로 만들기 (0) | 2018.01.26 |
[1149] RGB 거리
기본 DP2
- d[n][k] : n번째 집을 컬러 k로 칠했을 때, 1~n번째 집을 칠하는데 드는 최소비용.
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 | #include <stdio.h> int rgb[1001][3]; int d[1001][3]; int min(int a, int b) { return a > b ? b : a; } int go(int n, int k) { int ans; if(n == 0) return rgb[0][k]; if(d[n][k]) return d[n][k]; if(k == 0) { ans = go(n-1, 1); ans = min(ans, go(n-1, 2)); } else if(k == 1) { ans = go(n-1, 0); ans = min(ans, go(n-1, 2)); } else { ans = go(n-1, 0); ans = min(ans, go(n-1, 1)); } return d[n][k] = ans + rgb[n][k]; } int main() { int i, j, n; int ans; scanf("%d", &n); for(i=0; i<n; i++) for(j=0; j<3; j++) scanf("%d", &rgb[i][j]);; ans = go(n-1, 0); ans = min(ans, go(n-1, 1)); ans = min(ans, go(n-1, 2)); printf("%d\n", ans); return 0; } | cs |
>> 실은 6개월전에 해결했던 문제다.
하지만 과거에 코드를 보니, 한동안 ps를 안해서 그런지 더 멍청해진것 같다는 생각이 든다...
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> int rgb[1001][3], d[1001][3]; int min(int a, int b) { return a > b ? b : a; } int go(int n, int color) { int ret; if(n < 0) return 0; if(d[n][color]) return d[n][color]; ret = go(n-1, (color+1)%3); ret = min(ret, go(n-1, (color+2)%3)); return d[n][color] = ret+rgb[n][color]; } int main() { int i, j, n, ans; scanf("%d", &n); for(i=0; i<n; i++) for(j=0; j<3; j++) scanf("%d", &rgb[i][j]); ans = go(n-1, 2); ans = min(ans, go(n-1, 1)); ans = min(ans, go(n-1, 0)); printf("%d\n", ans); return 0; } | cs |
- 백준해설
i번째 집의 이웃은 i-1번째 집과 i+1번째 집. (연속)
처음집과 마지막 집은 이웃이 아니다..!!
다이나믹에서 중요한 조건중에 하나인 "연속"이라는 조건이 포함된 문제..!!
앞의 집과의 색만 다르게 칠하면 된다.
- 아래 코드는 바텀업.
1 2 3 4 5 6 7 | for(int i=1; i<=n; i++) { d[i][0] = min(d[i-1][1], d[i-1][2]) + a[i][0]; d[i][1] = min(d[i-1][0], d[i-1][2]) + a[i][0]; d[i][2] = min(d[i-1][0], d[i-1][1]) + a[i][0]; } cout << min({d[n][0], d[n][1], d[n][2]}) << '\n'; | cs |
>> 0번째는 비워두고 하는것이 좋다.
>> min({a, b, c}); // a, b, c 중 최소값.
>> c++11 문법으로 아래가 함수의 원형인 것 같다. 즉 리스트로 들어가서 그 리스트들 중 최소값이
리턴되는 방식인 것 같다.
template<class T> T min( std::initializer_list<T> ilist) { return *std::min_element(ilist.begin(), ilist.end()); }
'BOJ > DP' 카테고리의 다른 글
[2302] 극장 좌석 (0) | 2018.02.05 |
---|---|
[1937] 욕심쟁이 판다 (0) | 2018.02.01 |
[1309] 동물원 (0) | 2018.02.01 |
[1932] 숫자삼각형 (0) | 2018.02.01 |
[1463] 1로 만들기 (0) | 2018.01.26 |
[1463] 1로 만들기
DP1 - basic
- go(n) : 3개의 연산을 적절히 사용했을 때, n을 1로 만드는 회수의 최소값.
< 소스코드 - top 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 | #include <stdio.h> #define INF 0x3f3f3f3f int d[1000001]; int go(int n) { int a, b, c, ans; a = b = c = INF; if(n == 1) return 0; if(d[n]) return d[n]; if(n%3 == 0) a = go(n/3)+1; if(n%2 == 0) b = go(n/2)+1; c = go(n-1)+1; ans = a < b ? a : b; ans = ans < c ? ans : c; return d[n] = ans; } int main() { int n; scanf("%d", &n); printf("%d\n", go(n)); return 0; } | cs |
< 소스코드 - bottom up >
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | #include <stdio.h> int main() { int i, n, d[1000001]; scanf("%d", &n); d[1] = 0; for(i=2; i<=n; i++) { d[i] = d[i-1] + 1; if(i%2 == 0 && d[i] > d[i/2]+1) d[i] = d[i/2]+1; if(i%3 == 0 && d[i] > d[i/3]+1) d[i] = d[i/3]+1; } printf("%d\n", d[n]); return 0; } | cs |
-
'BOJ > DP' 카테고리의 다른 글
[2302] 극장 좌석 (0) | 2018.02.05 |
---|---|
[1937] 욕심쟁이 판다 (0) | 2018.02.01 |
[1309] 동물원 (0) | 2018.02.01 |
[1932] 숫자삼각형 (0) | 2018.02.01 |
[1149] RGB 거리 (0) | 2018.01.30 |