[백준 11057 - C++] 오르막 수 : 다이나믹 프로그래밍 (DP)

www.acmicpc.net/problem/11057

11057번: 오르막 수

문제

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.

예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

 

입력

첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.

 

출력

첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1 

1

예제 출력 1 

10

 

예제 입력 2 

2

예제 출력 2 

55

 

예제 입력 3 

3

예제 출력 3 

220

 

풀이

i번째 숫자는 i-1번째 숫자보다 크거나 같아야한다.

따라서 i번째 숫자가 j이기 위해서는 i-1번째 수가 0~j 여야한다.

이때, i-1번째 수가 0 ~ j-1 인 경우의 수는 i번째 숫자가 j-1인 경우의 수와 같다,

즉 i번째 수가 j-1인 경우에 i-1번째 수가 j인 경우만 더하면 i번째 수가 j인 경우의 수가 되는 것이다.

이를 식으로 나타내면

i (i<=2) 자리 수의 경우

j = 0인 경우 : f( i , 0 ) = f( i-1 , 0)

j != 0인 경우 : f(i , j) = f(i-1, j) +f( i , j-1 )

가 된다. 이를 코드상에 표현해 주면 끝나는 문제이다.

 

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
int cnt[1001][10];

int main(void){
    int n;
    int sum = 0;
    scanf("%d", &n);
    for(int i=0; i<10; i++){
        cnt[1][i] = 1;
    }
    for(int i=2; i<=n; i++){
        cnt[i][0] = cnt[i-1][0] % 10007;
        for(int j=1; j<10; j++){
            cnt[i][j] = cnt[i][j-1] + cnt[i-1][j];
            cnt[i][j] %=10007;
        }
    }
    for(int i=0; i<10; i++){
        sum+=cnt[n][i];
    }
    printf("%d\n", sum%10007);
}