[BOJ-10844][C++] 쉬운 계단 수

문제

45656이란 수를 보자.

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

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

 

입력

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

 

출력

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

 

예제 입력 1 

1

 

예제 출력 1

9

 

예제 입력 2 

2

 

예제 출력 2 

17

 

알고리즘 분류

• 다이나믹 프로그래밍

 

문제 출처

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

10844번: 쉬운 계단 수

 

---

 

문제 해결 방법

• DP를 이용하여 문제를 해결하였다.

 

점화식 구하기

• 이 문제의 해결을 위한 핵심은 다음과 같다.

① 길이가 @N - 1@인 숫자의 마지막 자리 숫자(@X@)가 @0@일 경우, 길이가 @N@인 숫자는 그 뒤에 @1@만 붙일 수 있다. (예 : 01) ② 길이가 @N - 1@인 숫자의 마지막 자리 숫자(@X@)가 @9@일 경우, 길이가 @N@인 숫자는 그 뒤에 @8@만 붙일 수 있다. (예 : 98) ③ 길이가 @N - 1@인 숫자의 마지막 자리 숫자(@X@)가 @1@ ~ @8@일 경우, 길이가 @N@인 숫자는 그 뒤에 @X - 1@ 또는 @X + 1@을 붙일 수 있다. (예: 10, 12 또는 87, 89)

• 우선 한 자릿수(@N = 1@)는 @1@, @2@, @3@, @4@, @5@, @6@, @7@, @8@, @9@으로, 총 9가지가 있다.
• @N@이 각각 @1@, @2@, @3@일 때, 위의 조건을 이용하여 쉬운 계단 수를 구해보자.

 

@N = 1@일 경우

• 총 9가지

N	X
1	1	2	3	4	5	6	7	8	9

 

@N = 2@일 경우

• 총 17가지

N	X
1	1	2	3	4	5	6	7	8	9
2	10	21	32	43	54	65	76	87	98
	11	23	34	45	56	67	78	89

 

@N = 3@일 경우

• 총 32가지

N	X
1	1	2	3	4	5	6	7	8	9
2	10	21	32	43	54	65	76	87	98
	11	23	34	45	56	67	78	89
3	101	210	321	432	543	654	765	876	987
		212	323	434	545	656	767	878	989
	110	212	343	454	565	676	787	898
	112	234	345	456	567	678	789

 

• 따라서 위의 조건을 이용하여 점화식을 구하면 다음과 같다.

$N : \text{자릿수}, \; X : \text{마지막 자리 숫자}$
$$dp[N][X] = \begin{cases} dp[N - 1][1] & \text{(if   X = 0)} \\ dp[N - 1][8] & \text{(if   X = 9)} \\ dp[N - 1][j - 1] + dp[N - 1][j + 1] & \text{Otherwise}   \end{cases}$$

 

DP 테이블 만들기

• DP 테이블은 @dp[N][X]@와 같이 정의한다. (@N@ : 자릿수, @X@ : 마지막 자리 숫자)
• 100자리의 수까지 계속 누적하면서 DP 테이블을 채워나가야 하기 때문에, 가장 큰 자료형(@unsigned long long@)을 사용한다.

ULL dp[101][10];

• 문제에서 @100,000,000@으로 나눈 나머지를 출력하려고 했으므로, 위에서 구한 점화식을 다음과 같이 수정해준다.

$N : \text{자릿수}, \; X : \text{마지막 자리 숫자}$
$$dp[N][X] = \begin{cases} dp[N - 1][1] & \text{(if    X = 0)} \\ dp[N - 1][8] & \text{(if    X = 9)} \\ (dp[N - 1][j - 1] + dp[N - 1][j + 1]) \; \text{%} \; 1000000000 & \text{Otherwise} \end{cases}$$

• 코드로 표현하면 다음과 같다.

int Solution(int n) {
    ULL result = 0;

    // 한 자릿수의 경우 (A = 1)
    for (int i = 1; i <= 9; i++) {
        dp[1][i] = 1;
    }

    // 두 자릿수 이상인 경우 (A >= 2)
    for (int i = 2; i <= n; i++) {
        dp[i][0] = dp[i - 1][1];    // 마지막 숫자가 0인 경우, 그 뒤에 1만 올 수 있다.
        for (int j = 1; j <= 8; j++) {
            dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD;   // 마지막 숫자가 1~8인 경우, 그 뒤에 숫자가 2개 (j - 1 또는 j + 1) 올 수 있다.
        }
        dp[i][9] = dp[i - 1][8];    // 마지막 숫자가 9인 경우, 그 뒤에 8만 올 수 있다. 
    }

    for (int i = 0; i <= 9; i++) {
        result += dp[n][i];
    }

    result %= MOD;

    return result;
}

 

코드

#include <iostream>
using namespace std;

#define MOD 1000000000
using ULL = unsigned long long;

int N;
ULL dp[101][10];    // dp[N][X], N : 자릿수, X : 마지막 자리 숫자

void Input() {
    cin >> N;
}

int Solution(int n) {
    ULL result = 0;

    // 한 자릿수의 경우 (A = 1)
    for (int i = 1; i <= 9; i++) {
        dp[1][i] = 1;
    }

    // 두 자릿수 이상인 경우 (A >= 2)
    for (int i = 2; i <= n; i++) {
        dp[i][0] = dp[i - 1][1];    // 마지막 숫자가 0인 경우, 그 뒤에 1만 올 수 있다.
        for (int j = 1; j <= 8; j++) {
            dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % MOD;   // 마지막 숫자가 1~8인 경우, 그 뒤에 숫자가 2개 (j - 1 또는 j + 1) 올 수 있다.
        }
        dp[i][9] = dp[i - 1][8];    // 마지막 숫자가 9인 경우, 그 뒤에 8만 올 수 있다. 
    }

    for (int i = 0; i <= 9; i++) {
        result += dp[n][i];
    }

    result %= MOD;

    return result;
}

void Output() {
    cout << Solution(N) << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Input();
    Output();

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [동적 계획법 1]
• 실버I