728x90
반응형
DP 문제이다.
문제의 포인트는 0부터 시작할 수 있다는 것과 오름차순 수열, 그리고 인접한 수가 같아도 된다는 것이다.
자릿수가 1일 때,
0 1개
1 1개
2 1개
...
9 1개
로 10개이고,
자릿수가 2일 때,
수열의 마지막 수 | 다음에 올 수 있는 수 |
0 | 0,1,2,3...9 |
1 | 1,2,3,4...9 |
2 | 2,3,4,5...9 |
... | ... |
9 | 9 |
총 55개 라는 것이다.
그럼 수열의 마지막 수를 j라 하고 올 수 있는 수를 k라 했을 때,
j에서 k만큼의 경우의 수를 더한다는 것을 알 수 있다.
코드로 표현해보면 이렇다.
// 오르막수
#include <iostream>
using namespace std;
int main(void){
int count, total = 0,dp[1001][10] = {0};
cin >> count;
for(int i = 0; i < 10; i++){
dp[1][i] = 1;
}
for(int i = 2; i <= count; i++){
for(int j = 0; j < 10; j++){
for(int k = j; k < 10; k++){
dp[i][j] = (dp[i][j] + dp[i - 1][k]) % 10007;
}
}
}
for(int i = 0; i < 10; i++){
total = (total + dp[count][i]) % 10007;
}
cout << total;
}
반응형
'algorithm' 카테고리의 다른 글
[algorithm] 백준 - 가장 긴 증가하는 부분 수열 1 & 4 (0) | 2020.11.03 |
---|---|
[algorithm] 백준 - 스티커 (0) | 2020.11.02 |
[algorithm] 백준 - 쉬운 계단 수 (0) | 2020.11.02 |
[algorithm] 백준 - 1,2,3 더하기 5 (0) | 2020.11.02 |
[algorithm] 백준 - 카드 구매하기 (0) | 2020.11.02 |