챕터3-9. DP | 문제 풀이2 - (3) 백준 No.11057 : 오르막 수

오르막 수 문제

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

문제요약

'오르막 수'는 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.
ex) 2234, 3678, 1119
수의 길이 N이 주어졌을 때, '오르막 수'의 개수를 구하는 프로그램을 작성하시오.
출력은 10007로 나눈 나머지 값을 출력하시오.

해결 방법

1. D[N] 에 어떤 값을 저장할 것인지 문장으로 정의해줘야 한다.
- D[N] = "길이가 N인 오르막 수의 개수"
   수의 각 자리에는 0 ~ 9가 올 수 있기 때문에 좀 더 세분화 할 수 있도록 2차원 배열로 다음과 같이 정의해준다.
   D[N][L] = "길이가 N이고 수 L으로 끝나는 오르막 수의 개수"

 

2. D[N]의 값을 어떻게하면 찾을 수 있을지 점화식을 생각한다.
- 정수 N이 주어지고, 앞에 어떤 조합이 존재하고 마지막 조합에서 아래와 같은 방법 중 1가지를 선택할 수 있다.

.....0으로 끝나는 경우 : D[N][0] = D[N-1][0]

.....1으로 끝나는 경우 : D[N][1] = D[N-1][0] + D[N-1][1]

.....2으로 끝나는 경우 : D[N][2] = D[N-1][0] + D[N-1][1] + D[N-1][2]

(생략)

.....9으로 끝나는 경우 : D[N][9] = D[N-1][0] + D[N-1][1] + D[N-1][2] + ... + D[N-1][9]

 

따라서 점화식은 D[N] = D[N][0] + D[N][1] + D[N][2] + ... + D[N][9] 이다.

 

3. 다이나믹 프로그래밍 방법을 적용할 수 있는 문제인지 확인 => 1, 2번을 거쳐야 이게 잘 보임.
- 위와 같이 큰 문제를 작은 문제로 쪼갤 수 있으며, 작은 문제도 큰 문제와 같은 방법으로 풀 수 있고, 작은 문제들이 겹친다.
   (Overlapping SubProblem)
- 문제의 정답을 작은 문제의 정답으로부터 구할 수 있으며, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.
   (Optimal Substructure)

 

4. 코드구현

- D[1]일 때 d[1][0] = 1, d[1][1] = 1, d[1][2] = 1, ....., d[1][9] = 1 초기화 해주어야 한다.
- 10007로 나눈 나머지를 출력하는 문제이므로 배열 d에 값을 넣을 때 10007로 나눈 나머지를 저장하는 것을 잊지말자.

<Top-down 방식>

2차원 배열을 사용하였으므로 그냥 Bottom-up방식 사용할 것.

<Bottom-up 방식>

(1) 구현
-> 'for문을 이용한 반복문'으로 구현

#include <iostream>

using namespace std;

int d[1001][10];

int main()
{
    int n;
    cin >> n;

    // d[1][0~9], "길이가 1이고 0~9로 끝나는 수"에 대한 값 초기화
    for (int i = 0; i <= 9; i++)
        d[1][i] = 1;

    // d[n][0] ~ d[n][9]를 점화식을 이용해서 계산
    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];
                d[i][j] %= 10007;
            }
        }
    }

    // d[n][0] ~ d[n][9] 를 모두 더하여 "길이가 N일 때 오름수의 개수"를 구함
    int sum = 0;  
    for (int i = 0; i <= 9; i++)
    {
        sum += d[n][i];
        sum %= 10007;
    }
    
    cout << sum;
}

 

(2) 시간복잡도
= for 문의 반복 횟수 
= O(N)