[BOJ] 10844번 : 쉬운 계단 수 (C++)

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

10844번: 쉬운 계단 수

dp문제이다.

dp문제는 테이블을 정의하는 것이 너무나 중요하다. 

이번 문제도 테이블만 잘 정의하면 어렵지 않게 문제를 풀어나갈 수 있는데, 중요한 건 테이블을 정의하는 게 쉽지 않다는 것이다. 

 

우선, 계단 수를 생각해보자. 

길이가 1인 계단 수는 1, 2, 3, 4, 5, 6, 7, 8, 9 이렇게 총 9개가 있다. 

그리고 길이가 2인 계단수는 1로 부터 10,12 / 2->21,23 / 3->32,34 / ... / 8->87,89 / 9->98 가 있다. 

현재 1~8까지는 각각 2개의 계단수를 생성하였고, 9에서만 1개의 계단수를 생성하였다.

길이가 3인 계단수를 살펴보자.

10 -> 101 / 12 -> 121, 123 / 21 -> 210, 212 / ... / 89 -> 898 / 98 -> 987,989 가 생긴다.

이렇게 살펴보다보면 알 수 있는 특징이 있다. 

0,9로 끝난 수로부터는 1개의 계단수가 생기고,

1~8로 끝난 수로부터는 2개의 계단수가 생긴다는 것이다. 

이로부터 다음과 같은 테이블을 생성해낼 수 있다. 

d[a][b]=k : 길이가 a인 계단수의 마지막 숫자가 b인 수가 총 k개 있다. 

그렇다면 b가 0일 때와 9일 때만 특별하게 봐주면 된다.

현재 수의 마지막 숫자가 0이려면 끝자리가 1인 수로부터 나온 것이다.

따라서 d[a][0] = d[a-1][1] 이 만족된다.

현재 수의 마지막 숫자가 9이려면 끝자리가 8인 수로부터만 만들어질 수 있다.

따라서 d[a][9] = d[a-1][8] 이 만족된다.

나머지 숫자는 b-1, b+1 이렇게 양쪽수로부터 만들어졌다.

 

추가로 연산하다보면 수가 매우 커질 수 있어서 연산 중간중간 모듈러 연산을 해줘야 한다. 

 

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int d[102][10]; //d[a][b]=k : 길이가 a인 계단수 중 마지막 숫자가 b인 수가 총 k개이다.

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;
    for(int i=1; i<=9; i++) d[1][i]=1;

    for(int i=2; i<=n; i++){
        for(int j=0; j<=9; j++){
            if(j==0) d[i][j] = d[i-1][1] % 1000000000;
            else if(j==9) d[i][j] = d[i-1][8] % 1000000000;
            else d[i][j] = (d[i-1][j-1]+d[i-1][j+1]) % 1000000000;
        }
    }

    int ans=0;
    //길이가 n인 계단수 출력
    for(int i=0; i<=9; i++){
        ans = (ans+d[n][i])%1000000000;
    }

    cout<<ans;

    return 0;
}