[백준] 10844 쉬운 계단 수 - 다이나믹 프로그래밍

[ 문제링크 ]

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

 

🚩 조건

1. 계단 수는 45656처럼 인접한 모든 자리의 차이가 1인 수를 뜻함
2. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해라
3. 그걸 1,000,000,000으로 나눈 나머지를 출력해라

 

 

🚩 접근

현재 자리의 수가 1이면, 뒤에 올 수 있는 수는 0과 2이다. 0과 9라는 예외가 있지만 0~9까지의 수는 모두 비슷한 양상을 띈다. 그래서 점화식을 세울 수 있지 않을까? -> DP

 

 

🚩 시행착오

 점화식을 찾아내는 데 굉장히 많은 시간을 들였다.. D[i]를 i 뒤에 나올 수 있는 수 개수로 놔둬보기도 하고, F[i]는 길이가 i인 0으로 시작하는 것도 포함한 계단 수/D[i]는 0으로 시작하는 계단 수 로 놔둬서 빼보기도 하고..ㅎ

 어렵다고 생각이 든 이유는 0과 9는 다른 수와 다른 양상을 보이기 때문이었는데, 그래서 D라는 테이블은 길이뿐만 아니라 시작하는 수에 대한 정보도 포함해야 한다는 생각이 들었다. 그래서 길이가 i고 j로 시작하는 계단 수의 개수를 저장하는 D[i][j]라는 테이블을 정의했다.

 

그리고 초기값으로 i가 1, 2일 때 0~9의 j에 대해 문제에서 주어진대로 설정해주었고, 이후 점화식을 계산할 때 j가 0 또는 9일 경우 0이 되도록 예외처리? 해주었다.

그리고 오버플로우 방지를 위해 계산 중간중간에 1,000,000,000에 대한 % 연산을 해주었다.

 

난 이 풀이가 뭔가 비효율적이라 생각해서 풀고난 후 다른 풀이를 찾아봤는데, 이 풀이가 대부분이었다..

 

 

💻 코드 (C++)

#include <iostream>
using namespace std;

int D[101][10];    //1-indexed, 0-indexed
int sum;

int main(){
    for(int i=0; i<10; i++){
        if(i==0){
            D[1][i]=0;
            D[2][i]=1;
        }else if(i==9){
            D[1][i]=1;
            D[2][i]=1;
        }else{
            D[1][i]=1;
            D[2][i]=2;
        }
    }
    
    int n;
    cin>>n;
    
    for(int i=3;i<=n;i++){
        for(int j=0;j<10;j++){
            if(j==0)
                D[i][j]=0+D[i-1][j+1];
            else if(j==9)
                D[i][j]=D[i-1][j-1]+0; 
            else
                D[i][j]=D[i-1][j-1]+D[i-1][j+1]; 
            D[i][j]%=1000000000;
        }
    }
    
    for(int i=1;i<10;i++){
        sum+=D[n][i];
        sum%=1000000000;
    }
    cout<<sum;
}