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

 

 

문제

45656이란 수를 보자.

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

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

입력

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

출력

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

 

접근 방식

 

dp[i][j] 는 i자리 숫자에서 마지막 숫자가 j인 계단 수의 개수이다

예를들어 dp[2][1] 라면 2자리 숫자 중 마지막 숫자가 1인 계단 수의 개수인것이다

 

i자리 계단 수에서 마지막 숫자가 j라면, 이전자리 숫자인 i-1은 숫자가 j-1 또는 j+1이어야 한다

 

따라서, 점화식을 구하자면

dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] 이다.

 

하지만, 숫자가 0이거나 9일 때 

0은 이전 자리 숫자가 1만 가능하고

9는 이전 자리 숫자가 8만 가능하므로 이를 주의해야 한다

 

점화식을 알고나면 쉽지만.. 역시 dp 문제는 어렵다 ^^..

 

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N; cin>>N;

    ll dp[103][103];

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

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

    ll res = 0;
    for(int j=0; j<=9; j++) {
        res = (res + dp[N][j]) % 1000000000;
    }

    cout<<res;
}