https://www.acmicpc.net/problem/10844
이 문제는 Bottom-up 방식으로 풀었습니다.(밑에서부터 차근차근~)
DP를 2차원 배열로 연습하고 싶으신 분께 좋은 것 같습니다.
저와 같은 사람들은 변수 선언시 무조건 int로 했었는데
이런 문제에서 long long 타입 선언을 간과하면 안되겠구나.. 하는 것을 깨닫게 해주었습니다.
Top-down
#include <iostream>
#include <cstdio>
using namespace std;
long long d[101][10];
int main() {
int n;
long long result = 0;
scanf("%d", &n);
for (int i = 1; i <= 9; i++) {
d[1][i] = 1;
}
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= 9; j++) {
if (j == 9) {
d[i][j] = d[i - 1][j - 1];
}
else if (j == 0) {
d[i][j] = d[i - 1][j + 1];
}
else {
d[i][j] = d[i - 1][j - 1] + d[i - 1][j + 1];
}
d[i][j] %= 1000000000;
}
}
for (int i = 0; i <= 9; i++) {
result += d[n][i];
}
result %= 1000000000;
printf("%d\n", result);
return 0;
}
- 혼잣말
DP는 항상 문제가 짧아서 쉬워보여도 정말 어려운 것같다…
처음에 2차원배열을 생각 못해서 다른분의 도움을 받았다.
다음은 long long을 생각 못해서 계속 왜맞틀했다….