[BOJ] 백준 11057 오르막 수 / 동적 계획법(Dynamic-Programming)

이미지를 클릭하면 문제 사이트로 이동합니다.

---

 

 

💣 문제 이해

 

 

1. 2234와 3678, 11119 와 같이 인접한 수가 같거나 오름차순을 이루는 수를 오르막 수 라고 정의한다.

2. 수는 0 으로 시작할 수 있다.

3. 입력으로 주어지는 N 자리 수에서 오르막 수의 갯수를 출력한다.

 

동적 계획법(Dynamic Programming) 방식을 사용했다.

 

 

 

 

💭 풀이 과정

 

 

N = 1 인 경우   0, 1, 2, 3, 4, 5, 6, 7, 8, 9  로 총 10 가지이다.

 

N = 2 인 경우  00~09, 11~19, 22~29, .... , 88~89, 99 로 총 55 가지이다.

 

 

여기서 규칙을 찾아보면 2자리 수 (ab) 에서 일의 자리 수 (b) 는 십의 자리 수 (a) 와 같거나 크다는 것을 발견할 수 있다.

 

즉,, 0b 의 경우  b 는 0보다 크거나 같은 경우, 1b 는 1보다 크거나 같은 경우, .... 라는 것을 발견할 수 있다.

 

 

 

 

변화를 표로 보면 다음과 같다.

 

	0	1	2	3	4	5	6	7	8	9
N = 1	1	1	1	1	1	1	1	1	1	1
N = 2	10	9	8	7	6	5	4	3	2	1

 

 

도표 보이는 그대로 2차원 배열로도 풀이 가능하나, 1행짜리 배열로 처리하고 싶은 마음에 그렇게 짜보았다.

 

점화식은 dp[i] = dp[i] + dp[j] 이다.  ( i 가 0 이라면 j 는 0~9, i 가 1 이라면 j 는 1~9 )

 

이 점화식에 따라 N = 3 은 다음과 같다.

 

N = 3

55

45

36

28

21

15

10

6

3

1

 

둘째 자리가 0인 경우, 10 + 9 + 8 + 7 + ... + 1 = 55 가 되고,

둘째 자리가 1인 경우, 9 + 8 + 7 + ... + 1 = 45 가 되고,

둘째 자리가 2인 경우, 8 + 7 + 6 + ... + 1 = 36 이 되는 이런 방식이다.

 

 

 

 

 

작성 언어: C++

 

#include <cstdio>
#include <algorithm>    // std::fill_n
#define mod 10007

int dp[10] = {0, };

int solve(int num){
    int retVal = 0;
    // N = 2 이면 dp 배열을 한 번 더 채워야하고 N = 3 이면 dp 배열을 두 번 더 채워야한다. -2 한 횟수 루프
    for (int k = 1; k <= num-1; ++k) {
        for (int i = 0; i < 10; ++i) {
            for (int j = i+1; j < 10; ++j) {
                dp[i] = (dp[i] + dp[j]) % mod;
            }
        }
    }
    // dp 배열의 총합이 N 자리 오르막수 개수
    for (int i = 0; i < 10; ++i) {
        retVal = (retVal + dp[i]) % mod;
    }
    return retVal;
}


int main(){
    int numLeng = 0, count = 0;
    std::fill_n(dp, 10, 1);
    scanf("%d", &numLeng);
    // 입력받은 N 자리수까지 계산할 것.
    count = solve(numLeng);
    printf("%d\n", count);
    return 0;
}

 

 

 

 

🏆 배운 점

 

 

바로 앞의 쉬운 계단 수와 비슷한 문제이다.

 

반복되는 문제를 풀면서 패턴이 조금씩 감이 잡히는 듯 하다.

 

많이 풀어보는 것이 중요한 이유가 이것인가보다.