Dynamic Programming(동적 계획법)의 개발절차
1. 재귀 관계식(recursive property) 세우기
2. 상향식 방법(bottom-up)으로 답 구하기
N=1일 때 0, 1, ⋯, 9까지 총 10개가 존재한다.
N=2일 때 오르막 수를 AB라고 두면, A는 0부터 9까지 가능하다. (0으로 시작할 수 있다는 조건에 의해)
그러면 A=0이고 B는 0~9, A=1이고 B는 1~9, ⋯, A=9이고 B는 9까지 총 55개가 존재한다.
재귀 관계식
DP[i][j] : 길이가 j이고 i로 시작하는 오르막 수의 개수
DP[i][j] = sum(DP[i][j-1] + DP[i+1][j-1] + ⋯ + DP[9][j-1])
int calNum(int n) {
int res = 10; // N = 1
for (int j = 1;j < n;j++) { // col
dp[0][j] = res;
for (int i = 1;i <= 9;i++) { // row
dp[i][j] = (dp[i-1][j] - dp[i - 1][j - 1] + 10007) % 10007;
res += dp[i][j];
res %= 10007;
}
}
return res;
}
- 가장 먼저 dp[0][j]는 이전 수행의 결과값으로 갱신한다.
- (A+B+C) % M = (A%M) + (B%M) + (C%M)
- 계산 중 overflow를 방지하기 위해 mod 10007을 해준다.
dp[i][j]를 계산하기 위해 뺄셈을 하는 과정에서, 음수 값이 발생할 수 있으므로 +10007을 해준다.
// init
for (int i = 0;i <= 9;i++) {
dp[i][0] = 1;
}
printf("%d", calNum(n));