[DP] 11057번 오르막 수

11057번 오르막 수

 

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

 

문제

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

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

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

 

입력

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

 

출력

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

 

예제 입력

1

2

3

 

예제 출력

10

55

220

 

해결방법

DP 문제이다.

d[n][0] : 0으로 끝나는 오르막 수

d[n][1] : 1로 끝나는 오르막 수

:

d[n][9] : 9로 끝나는 오르막 수

 

먼저 1자리 수 일 때, 오르막 수를 설정해준다

for(int i=0; i<=9; i++){
    d[1][i] = 1;
}

 

2자리 부터는 bottom-up 방식으로 DP를 구현한다

for(int i=2; i<=n; i++){
    for(int j=0; j<=9; j++){
        for(int k=0; k<=j; k++){
            d[i][j] += (d[i-1][k] % 10007);
        }
    }
}

 

d[n][0] ~ d[n][9] 까지의 합이 정답이므로 반복문을 통해 답을 구한다

ans = 0;
for(int i=0; i<=9; i++){
    ans += d[n][i];
}
cout << ans % 10007 << "\n";

 

소스코드

#include <iostream>
#include <cstring>
#include <math.h>
#include <algorithm>
#define MAX 1001
using namespace std;

int n,ans;
int d[MAX][10];

/*
 
 순환식 : 
 d[n][i] : d[n-1][0] + ... + d[n-1][i]
 
 */

void dp(){
    // 초기화
    for(int i=0; i<=9; i++){
        d[1][i] = 1;
    }
    
    for(int i=2; i<=n; i++){
        for(int j=0; j<=9; j++){
            for(int k=0; k<=j; k++){
                d[i][j] += (d[i-1][k] % 10007);
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    
    dp();
    
    ans = 0;
    for(int i=0; i<=9; i++){
        ans += d[n][i];
    }
    cout << ans % 10007 << "\n";
    
    return 0;
}