[BaekJoon, C++] 10844번 - 쉬운 계단 수

 

 

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

10844번: 쉬운 계단 수

 

 

#include <iostream>

using namespace std;


int main(){
    int n,sum = 0;
    cin>>n;
    int dp[101][10]; // i번째 자리의 수가 j인 계단수의 개수

    for(int i=1; i<10; i++){
        dp[1][i] = 1;
    }

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

    for(int i=0; i<=9; i++){
        sum += dp[n][i];
        sum %= 1000000000;
    }
    cout<<sum % 1000000000;
}

 

 

전형적인 DP 문제처럼 dp[i][j] 형태의 배열을 이용하려고 했다. 이 배열의 의미는 i번째의 수가 j인 계단 수의 개수이다.

계단 수의 최대 길이는 100 이므로 dp[101][10] 을 생성하였다.

배열은 0부터 세기 때문에 100번째 자리의 수에 대한 계단 수를 세기 위해서는 길이가 101인 배열이 필요하다. 

 

길이가 1인 계단 수의 개수는 모두 1개이므로 for문을 이용해 값을 미리 지정해주었다.

 

 

dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

n이 2 이상일 때는 케이스를 나눠줘야 한다. 

i번째 자리의 수가 j (2 <=j <=8)일 때에는 i-1번째 수가 j-1인 경우,  j+1인 경우가 있다.

 

 

 

그 외의 경우(j = 9 , j = 0)는 두 가지의 경우 중 한 가지만 가능하므로 따로 케이스를 나누어 주었다. 

그리고 변수 sum을 이용하여 n번째 자리의 수가 0 ~ 9 인 계단 수의 개수를 더해주었다.

이 과정에서 sum의 크기가 매우 커질 가능성이 있고,

구하려는 값이 sum을 1000000000으로 나눈 나머지의 값을 구하는 것이므로

미리 나누어 주었고 마지막으로 출력을 할 때에도 나누어 주었다.