[백준 10844, 11057] 쉬운 계단 수, 오르막 수 (DP, 점화식)

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

10844번: 쉬운 계단 수

'쉬운' 계단 수 라길래 호기롭게 도전했다가 실패.. DP를 공부하게 만들어준 문제

다른 블로그들의 설명을 봐도 이해가 안되길래 몇시간을 끙끙댔는데, 경우의 수들을 직접 표로 정리하고나서야 이해가 됐다.ㅠ

 

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

예제 입력 1 

1

예제 출력 1 

9

예제 입력 2 

2

예제 출력 2 

17

---

자릿수와 관계없이, 모든 계단수의 끝에는 0~9까지만 올 수 있다.

0뒤에는 1만, 9뒤에는 8만 올 수 있으며 1~8은 각각 '+1'한 값과 '-1'한 값이 오는 것으로 고정되어 있음을 알 수 있다.

 

'계단수의 개수'는 '계단수의 길이'와 '마지막자리의 값'에 따라 값이 달라지므로, 이중배열을 이용하여 풀이한다.

배열 dp[x][i] 는 계단수의 길이가 x이고 마지막 자리의 값이 i인 계단수의 개수를 의미한다.

 

길이가 2, 마지막 자리가 3인 계단수는 >> 23, 43

길이가 2, 마지막 자리가 5인 계단수는 >> 45, 65

길이가 3, 마지막 자리가 4인 계단수는 >> 234, 434, 454, 654

 

앞에서 구했던 값을 기억하는 DP의 특징을 보기 쉽게 배경색으로 구분해보았다.

마지막 자리 값이 4인 계단수는 직전 값이 3 또는 5만 가능하다.

즉, 길이가 2이고 마지막 자리가 3과 5인 계단수 뒤에 '4'를 붙이면 길이가 3이고 마지막 자리가 4인 계단수를 만들 수 있다!

이해를 돕기 위해 길이가 1, 2, 3 일때의 계단수를 표를 이용하여 정리해보았다.

dp[n][0]일때는 dp[n-1][1]에서만 앞부분을 가져올 수 있고 dp[n][9]일때는 dp[n-1][8]에서만 앞부분을 가져올 수 있다는 것을 유의하자.

(민트색 화살표는 끝값의 앞부분을[n-1][i-1], [n-1][i+1]에서 가져왔음을 보여준다.)

 

---

백준 10844번 소스코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
int main() {
    int n;
    int sum = 0;
    int dp[101][10] = { 0, };
    scanf("%d", &n);
 
    for (int i = 1; i < 10; i++) {
        dp[1][i] = 1;
   }
//dp[x][i]
    for (int x = 2; x <= n; x++) { //x는 계단수의 길이
        for (int i = 0; i < 10; i++) { //i는 마지막 자리의 수
            if (i == 0) 
                dp[x][i] = (dp[x - 1][1]) % 1000000000;
            else if (i == 9)
                dp[x][i] = (dp[x - 1][8]) % 1000000000;
            else
                dp[x][i] = (dp[x - 1][i - 1] + dp[x - 1][i + 1]) % 1000000000;
        }
    }
 
    for (int i = 0; i < 10; i++) {
        sum = (sum + dp[n][i]) % 1000000000;
    }
    printf("%d", sum);
}

 

---

백준 11057번 또한 문제 풀이 방식이 10844번 문제와 비슷하여, 똑같이 표를 그려 규칙을 찾으면 된다.

dp[x][i] = dp[x-1][0] + dp[x-1][1] ~~ + dp[x-1][i]로, [x-1]에서 끝값이 '0'부터 'i'까지 모두 더한 값과 같다.

 

---

백준 11057번 소스코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
int main() {
    int n;
    int result = 0;
    int dp[1001][10] = { 0, };
    scanf("%d", &n);
 
    for (int i = 0; i < 10; i++) {
        dp[1][i] = 1;
    }
 
    //dp[x][i]
    for (int x = 2; x <= n; x++) { //x는 계단수의 길이
        for (int i = 0; i <= 9; i++) { //i는 마지막 자리의 수
            long sum = 0;
            for (int k = 0; k <= i; k++)
                sum += dp[x - 1][k];
            dp[x][i] = sum % 10007;
        }
    }
    for (int i = 0; i < 10; i++) 
        result += dp[n][i];
 
    printf("%d", result % 10007);
}