[알고리즘] 백준 10844 쉬운 계단수 DP

DP안녕하십니까 감자 코딩에 감자 개발자입니다.
이번에 살펴볼 문제는 백준 알고리즘 DP문제인 쉬운계단수 문제 입니다.
처음에 DP를 접근하시는 분이라면 조금 어려우실 수 도 있으십니다만, 천천히 같이 풀어보도록하죠.

1. 문제

쉬운 계단 수 성공
시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초    256 MB    35683    10788    7812    28.467%
문제
45656이란 수를 보자.

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

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

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

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

예제 입력 1 복사
1

예제 출력 1 복사
9

예제 입력 2 복사
2

예제 출력 2 복사
17

출처
문제를 만든 사람: baekjoon
알고리즘 분류
다이나믹 프로그래밍

2. 해결 방법

키워드

• 인접한 모든 자리수의 차이가 1

• 0 으로 시작하는 수는 없다.

• 길이가 N인 계단 수가 몇 개

여기서 가장 중요하게 살펴 보셔야 할것은 바로

인접한 모든 자리수의 차이가 1

이것이 과연 무엇을 나타내는 것일까요?

예를 들어보겠습니다.
N = 2 라고 가정을 해보고 진행하겠습니다.

1~99까지의 N값을 사용한다고 하였으므로,
N = 0 일 경우는 판단하지 않는다고 하였습니다.

N = 1
1,2,3,4,5,6,7....9 까지 진행되겠죠? 총 9개 입니다.

N = 2
10, 12, 21, 23 , 32, 34, 43 ....까지 진행 됩니다.

여기서 점화식을 도출 하셨을까요?

1~9의 수로 진행하면서  
N=2 일 경우에  
십의 자리의 수의 값에서 -1값과 +1 한값으로 지금 진행되고 있는것이 보이시나요?

이게 가장 중요한점입니다. 처음에 저도 접근하는데 어려움이 좀 있었는데요. 차근차근 생각해보니까 이러한 점화식을 도출해 낼 수 있었습니다. 그리고 가장 중요한점은 값이 1-9의 수로 진행하지만, N=1일 경우는 계단의 수가 아니라고 명시하였으며, 점화식이 1-8까지 진행할때 성립된다는 것입니다.

이게 무슨 말이냐? 계단수가 1은 아니라고 하였으므로 2부터 계단수를 측정하게 됩니다.  
0같은 경우는 n-1이 포함될 수 없고, 9 의 경우에는 n + 1이 포함될 수 없습니다.  
다시 말해 10, 12 같은경우는(10은 포함 되지 않고 12만 포함된다는 말이고) dp\[n\] = dp\[n-1\]\[k+1\]  
9같은 경우는 (98, 100)이 되면 100이 포함되지 않고 98만 포함된다는 말입니다. dp\[n\] = dp\[n-1\]\[k-1\]  
단, n = 1~99까지의 수 k는 1~9의 수를 나타냅니다

이제 이것들을 가지고 문제를 풀어보도록 하겠습니다.

dp[n] = dp[n-1] + dp[n+1]/ dp[n] = dp[n-1] + dp[n-1] 

3. 소스 코드

//
//  쉬운계단수10844.cpp
//  beakjoon_algorithm
//
//  Created by kgh on 19/04/2019.
//  Copyright © 2019 kgh. All rights reserved.
//
#include <stdio.h>
#include <iostream>
using namespace std;
// 1~n(1<=n<=100) , 1~9 까지의 계단수
// ***** 인접한 모든수의 차이가 1이난다!
long long dp[101][10];
long long mod = 1000000000;
int main(void){
    int n;
    cin >> n;
    // 0으로 시작하는 수가 없으니까 1인 수의 계단수는 1개이므로
    for(int i=1; i<=9; i++){
        dp[1][i] = 1;
    }
    /*
     N = 1
     => 1, 2,3,4,5,6,7,8,9
     N =2
     => 10,12, 21, 23 ,32 ,34 43, 45
     1) 이때 주의 할점은 문제에서 1은 계단수가 아니라고 정의 하였고
     2) 따라서, 점화식 L(1~8일때만 성립한다)
     3) 0이라고 하는것은 범위가 dp[1]만 허용되고,  9 는 -1을 한 8만 허용되므로
     */
    // 총 n의 계단수 찾기 위함
    for(int i=2; i<=n; i++){
        // 1~9까지의 값
        for(int j=0; j<=9; j++){
            dp[i][j] = 0;
            // n-1의 경우
            if(j-1 >= 0){
                dp[i][j] += dp[i-1][j-1];
            }
            // n+1의 경우
            if(j+1 < 10){
                dp[i][j] += dp[i-1][j+1];
            }
            // mod로 나눈 경우
            dp[i][j] %= mod;
        }
    }
    long long ans = 0;
    for(int i=0; i<=9; i++){
        ans += dp[n][i];        // 1~n까지의 수중에 계단수의 개수를 뽑아내기위해.
    }
    ans %= mod;
    cout << ans << '\n';
    return 0;
}

이상 쉬운 계단수 문제를 풀어 보았는데요, 절대 쉬운 계단수가 아니였습니다.
한번 더 원리에 대해서 생각해보시면서 이상 감자코딩에 감자개발자였습니다. 감사합니다.