[백준] 10844번. 쉬운 계단 수 C++

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

>문제 설명

문제

45656이란 수를 보자.

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

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

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

입력

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

출력

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

 

풀이

 각 자리 수마다 0~9까지의 숫자를 각각 생각해보면, 0과 9는 1 차이 나는 숫자가 1개씩, 1~8까지는 2개씩 가진다. 제일 앞자리 수부터 계산한다고 하면, 우선 0으로 시작하는 수는 없으므로 dp[0] = 0, dp[i] = 1로 셋팅해둔다. 그리고 자리 수를 한자리 씩 늘리며 dp를 새로 계산해주는데, 한자리 늘려 계산한건 우선 temp 배열에 담는다.

 

 예를 들어, 현재 2자리일 때 4가 나오는 경우를 계산 중이라 하면, temp[4] = dp[3]+dp[5]가 된다.

 

 밑의 코드는 반대로? 생각해서 dp배열을 기준으로 dp[3]일 때 temp[3+1]에 저장, dp[5]일때 temp[5-1] 저장. 이렇게 두 번 계산해준다. (설명은 위의 예시가 편해서....저렇게..ㅎ)

 

 잊지 말고 Modular 계산도 꼭 해주기!!

#define MOD 1000000000
#include <iostream>
#include <algorithm>
using namespace std;

int n;
long long dp[10] = {0, };

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

    for(int i=2; i<=n; i++){
        
        long long temp[10] = {0, };
        
        for(int j=0; j<10; j++){
            
            if(j==0) temp[j+1] = (temp[j+1] + dp[j]) % MOD;
            else if(j==9) temp[j-1] = (temp[j-1] + dp[j]) % MOD;
            else {
                temp[j-1] = (temp[j-1] + dp[j]) % MOD;
                temp[j+1] = (temp[j+1] + dp[j]) % MOD;
            }
        }
        
        copy(temp, temp+10, dp);
    }
    
    long long sum = 0;
    for(int i=0; i<10; i++){
        sum = (sum + dp[i]) % MOD;
    }
    
    cout<<sum%MOD<<"\n";

    return 0;
}