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 |