[백준 11057번] 오르막 수 (C++)

문제링크 : https://www.acmicpc.net/problem/11057

11057번: 오르막 수

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, result;
int dp[1001][10];
const int MOD = 10007;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N;
    for(int i=0; i<10; i++) dp[1][i] = 1; //가로줄 초기화
    for(int i=1; i<=N; i++) dp[i][0] = 1; //세로줄 초기화

    for(int i=2; i<=N; i++)
    {
        for(int j=1; j<10; j++)
        {
            dp[i][j] = (dp[i-1][j] + dp[i][j-1])%MOD; //규칙에 대한 점화식
        }
    }

    for(int i=0; i<10; i++)
    {
        result += dp[N][i];
    }

    cout << result%MOD;
    return 0;
}

DP 문제이다.

경우의 수를 직접 써보고 규칙을 찾아보았다.

규칙은 다음과 같다.

세로 : 길이(N) / 가로 : 자릿수 (0 ~ 9)
  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
4 1 4 10 20 35 56 84 120 165 220

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

초기화 값으로는 첫 가로줄과 세로줄이 1인 것을 볼 수 있다.

길이가 1인 숫자는 한 자릿수인 0 ~ 9 까지 밖에 없기에 각각 1이 될 수 밖에 없다. (가로)

그리고 끝 자리가 0인 경우는 앞에도 무조건 0만 올 수 있으므로 마찬가지로 1이 될 수 밖에 없다 (세로)

 

여기서 구한 값은 각 길이에 대한 현재 끝자리 수에 대한 값이므로 모든 가짓수를 구하려면 N에 대한 0~9의 모든 경우의 수를 더해주고 출력하면 된다.