728x90
반응형

DP 문제이다.
이 문제의 특징은 모든 자리수의 차이가 1이 난다는 것이다.
그렇다면,
마지막 자릿수 | 다음 자릿수 |
0 | 1 |
1 | 0, 2 |
2 | 1, 3 |
... | ... |
9 | 8 |
로 이루어질 수 있다.
n을 자릿수라고 생각했을 때,
n = 2 일 때,
12 10
21 23
...
98
n = 3 일 때,
121 120 101
210 212 232 234
...
989 987
이것을 점화식으로 표현해보면,
dp[n][i] = dp[n - 1][i - 1] + dp[n - 1][i + 1]
로 계속 쌓아나가는 과정을 볼 수 있다.
코드로는
// 쉬운 계단 수
#include <iostream>
using namespace std;
int main(void){
long long count, dp[101][10], total = 0;
cin >> count;
for(int i = 1; i < 10; i++){
dp[1][i] = 1;
}
dp[1][0] = 0;
for(int i = 2; i <= count; i++){
for(int j = 0; j < 10; j++){
if(j == 9){
dp[i][j] = dp[i - 1][j - 1];
}
else if(j == 0){
dp[i][j] = dp[i - 1][j + 1];
}
else{
dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1])% 1000000000;
}
}
}
for(int i = 0; i < 10; i++){
total = (total + dp[count][i])% 1000000000;
}
cout << total % 1000000000;
}
반응형
'algorithm' 카테고리의 다른 글
[algorithm] 백준 - 스티커 (0) | 2020.11.02 |
---|---|
[algorithm] 백준 - 오르막수 (0) | 2020.11.02 |
[algorithm] 백준 - 1,2,3 더하기 5 (0) | 2020.11.02 |
[algorithm] 백준 - 카드 구매하기 (0) | 2020.11.02 |
[algorithm] 백준 - 좋은 수열 (0) | 2020.10.30 |