[백준 11057 / C++] 오르막 수

dp 배열을 이용해서 풀면된다. 

 

[dp이차원 배열 ]

길이/끝자릿수	0	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1	1
2	1	2	3	4	5	6	7	8	9	10
3	1	3	6	10	15	21	28	36	45	55

예를 한번 들어보자. 

만약 길이가 3인 오르막수를 구하라고 하면 어떻게 체크를 해야할까? 

먼저 위의 표를 보면 길이를 나타내는 컬럼과 1~9까지의 자릿 수의 컬럼을 만들었다. 

 

각 길이의 해당 끝자릿 수의 경우의 수는

현재 길이의 이전 끝자릿 수의 경우의 수 + 이전 길이의 같은 끝자릿수의 경우의 수이다. 

 

즉, 위의 표에서 길이가 2이고 끝자릿 수가 1인 값은 2 이고,  (01,11)

길이가 3이고 끝자릿 수가 0인 값은 1 라는 것을 알 수 있다.  (000) 

그렇다면 길이가 3이고 끝자릿 수가 1인 경우의 수는 위의 두값을 합친 결과이다. (001, 011, 111) 3가지. 

dp[i][j] = dp[i-1][j] + dp[i][j-1]  

 

#include <iostream>
using namespace std;
int dp[1001][10]; 
int main()
{    
    int n; cin >> n; 
    for (int i = 0; i <= 9; i++)dp[1][i] = 1;
    for (int i = 2; i <= n; i++) {   
        for (int j =0; j <= 9; j++) {
            if (j == 0)dp[i][0] = 1; 
            else dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; 
            dp[i][j] %= 10007; 
        }       
    }
    int sum = 0; 
    for (int j = 0; j <= 9; j++) {
        sum += dp[n][j];
    }   
    cout << sum%10007; 
}

11057번: 오르막 수