[11057번] 오르막 수

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

우선 점화식을 먼저 밝히고 그에 따라 설명을 이어가 보겠다.

DP[a][b]에서 a는 a번째 값(a가 3이면 3번째를 의미), b는 a번째에 들어가는 숫자를 의미한다.

for (int i = 0; i <= 9; i++)

DP[1][i] = 1;

scanf("%d", &n);

for (int i = 2; i <= n; i++)

{

for (int j = 0; j <= 9; j++)

for (int k = 0; k <= j; k++)

DP[i][j] += DP[i-1][k] % 10007;

}

이것의 의미를 파악해보자.

for (int i = 0; i <= 9; i++)

DP[1][i] = 1;

이것은 1번째 일 때는 모두 오르막 수 가 1개라는 의미이다.

즉, 0일때도 1, 1일때도 1, 2일때도 1 ...

for (int i = 2; i <= n; i++)

{

for (int j = 0; j <= 9; j++)

for (int k = 0; k <= j; k++)

DP[i][j] += DP[i-1][k] % 10007;

}

이것의 의미는 i가 2, j가 0, k가 0일때는

DP[2][0] += DP[1][0] % 10007인데 2번째 값이 0일 때 오르막 수가 되는 DP 값은

1번째 값이 0일 때 오르막 수가 되는 DP값을 더해야 한다는 의미이다.

DP[2][1]은 DP[1][0] 그리고 DP[1][1]을 더해주어야 한다.

DP[3][2]은 DP[2][0], DP[2][1], DP[2][2] 값을 더해주어야 한다.

이러한 방식으로 점화식을 구성해 나가면 정답을 도출 할 수 있다.

 

소스 코드 : 

#include <iostream>
#include <cstdio>
 
using namespace std;
 
int DP[1001][11] ;
 
int main()
{
    int n;
 
    for (int i = 0; i <= 9; i++)
        DP[1][i] = 1;
 
    scanf("%d", &n);
 
    for (int i = 2; i <= n; i++)
    {
        for (int j = 0; j <= 9; j++)
            for (int k = 0; k <= j; k++)
                DP[i][j] += DP[i-1][k] % 10007;
    }
 
    for (int i = 0; i <= 9; i++)
        DP[n][10] += DP[n][i] % 10007;
 
    cout << DP[n][10] % 10007;
 
    return 0;
}
 
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>