[DP] 오르막 수 (11057)(C++)

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

11057번: 오르막 수

 

1. 문제 개요

 

수의 자리가 오름차순을 이루는 수를 오르막 수라고 할때, 수의 길이 N으로 만들 수 있는 오르막 수의 개수를 구하는 문제. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 1234, 1113 등이 오르막 수이다.

 

 

2. 입출력

 

 

 

3. 문제 풀이

 

N*M의 2차원 배열을 사용하여 N자리 오르막 수 중 숫자 M으로 끝나는 수의 개수를 구한 후, M=0부터 M=9까지를 합하여 정답을 구하였다. 2차원 배열은 다음과 같다.

 

	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

 

여기서 규칙은 다음과 같다. N자리 오르막 수 중 숫자 M으로 끝나는 수의 개수는 N-1자리 오르막 수 중에서 숫자 M과 같거나 작은 수로 끝나는 수의 합과 같다. 예를 들어 세 자리 오르막 수 중에 숫자 1으로 끝나는 수는 두 자리 오르막 수 중에 숫자 1로 끝나는 수와 숫자 0으로 끝나는 수의 합이므로 1+2=3이된다. 따라서 list[i][j] = list[i-1][j] + list[i-1][j-1] + list[i-1][j-2] ... 과 같이 표현할 수 있으며 이를 다르게 표현하면 list[i][j] = list[i-1][j] + list[i][j-1]이 된다.

 

이를 코드로 나타내면 다음과 같다. 재귀함수로 구현하였다.

 

int DP(int n, int idx) {
    if(n==1)
        return 1;
    if(idx==0)
        return 1;
    if(list[idx][n])
        return list[idx][n];

    list[idx][n] = DP(n-1,idx) + DP(n,idx-1);
    
    return list[idx][n]%10007;
}

 

 

4. 전체 코드

 

#include <algorithm>
#include <iostream>

using namespace std;

const int MAX = 1001;
int list[10][MAX];

int DP(int n, int idx) {
    if(n==1)
        return 1;
    if(idx==0)
        return 1;
    if(list[idx][n])
        return list[idx][n];

    list[idx][n] = DP(n-1,idx) + DP(n,idx-1);
    
    return list[idx][n]%10007;
}

int main(void) {
    int N;
    scanf("%d",&N);
    
    int ans = 0;
    for(int i=0;i<10;i++)
        ans += DP(N,i);
    
    printf("%d\n",ans%10007);
}

 

아직 배워가는 중이라 틀린 부분이 있을 수 있습니다. 지적할 부분이 있다면 댓글로 알려주시면 감사하겠습니다!!!