[11057] 오르막 수

https://www.acmicpc.net/problem/11057

계단수와 비슷하게 풀었다.

d[i][j] 에서 i는 자릿수, j는 오르막수의 마지막 수를 뜻한다.

가령, d[1][2]는 마지막 수가 2인 1자릿수를 가진 오르막 수다.

만약 마지막 수가 1이라면 1~9가 뒤에 올 수 있다.

만약 마지막 수가 2이라면 2~9가 뒤에 올 수 있다.

이런식으로 0부터 9(k)까지 반복문을 돌려 k >= j 일때 d[i][j] 에 d[i-1][k]를 모두 더해준다.

2017/07/01 - [코딩/알고리즘] - [10844] 쉬운 계단수

---

#include <cstdio>

using namespace std;

int mod = 10007;

long upNumber(int N){

int d[1001][11] ={};

for(int i = 0;i<10;i++){

d[1][i] = 1;

}

for(int i = 2;i<=N;i++){

for(int j = 0;j<10;j++){

for(int k = 0;k<10;k++){

if(k >= j)

d[i][j] += d[i-1][k];

d[i][j] %= mod;

}

}

}

long res = 0;

for(int i = 0;i<10;i++){

res += d[N][i];

res %= mod;

}

return res;

}

int main(){

int N;

scanf("%d",&N);

printf("%ld\n",upNumber(N));

}