백준 11057 - 오르막수(C++/동적계획법/DP/Dynamic Programming)

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

11057번: 오르막 수

 

문제

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.
예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.
수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

 

접근법

일단 MOD(출력값은 10,007 의 나머지임)가 등장 한것부터 일반적인 계산식으로는 시간초과&&맞는 자료형이 없을것 같다.

1000자리 자연수는 오르막수가 엄청 많을것이니 이럴때는 Dynamic Programming을 사용해야한다.

개인적으론, DP치고는 접근법이 상당히 쉬운 문제였다고 생각한다..(상당히 흔한 접근법중 하나이다)

 

나는 항상 DP를 풀때는 입력과 출력값을 쭉 적어두고 시작한다. 아무래도 다른 알고리즘들 보다는 생각해야할게 많다고 생각해서 그런가보다.

 

입력 1
0 1 2 3 4 5 6 7 8 9 

입력 2
00 01 02 03 04 05 06 07 08 09 (10)
11 12 13 14 15 16 17 18 19 (9)
22 23 24 25 26 27 28 29 (8)
....
99(1)

입력 3
000 001 002 003 004 005 006 007 008 009, 011  012 013 014 016 ... (55개) (입력 2값 모두사용 가능)

111,112,113,114,115,116,117,118,119,122,123......(45개) (입력 2값에서 0으로 시작하는거 제외 모두 사용가능)

222.223.224.225.226.227,228,229,233,234......     (36개) (입력 2값에서 0,1로 시작하는거 제외 모두 사용가능)

 

이쯤되면 벌써 패턴이 보이기 시작한다. 55+45+36+28+21+15+10+6+3+1 일것이고 답은 220일것이다.

백준의 예시 출력을 보니 맞는거 같다.

 

3중 for문을 사용하면 편할것 같다. 조건에서는 입력값이 1000까지 될수 있으므로 dp[1001][10]로 넉넉히 잡아둔다.

dp[i][j] 일것이며

i는 N번째 자리수를 나타내고

j는 index(0~9)로 시작하는 오름수의 갯수를 저장한다.

ex)

dp[i][7] 이라면 dp[i-1][7] + dp[i-1][8] + dp[i-1][9] 가 되도록 (i번째 자리수의 7로 시작하는 오름수의 개수)

 

코드는 아래와 같다.

코드

#include <iostream>

#define MOD 10007

using namespace std;

long long dp[1001][10];

int main()
{
    int N;
    cin >> N;
    for (int i = 0; i < 10; i++)
    {
        dp[0][i] = 1;
    }
    for (int i = 1; i < N; i++)
    {
        for (int j = 0; j < 10; j++)
        {  
            for (int k = j; k < 10; k++)
            {
                    dp[i][j] += dp[i - 1][k] % MOD;  
            }
        }
    }
    long long ans = 0;
    for (int i = 0; i < 10; i++)
        ans += dp[N - 1][i];
    cout << ans % 10007;
}