[백준] 10844.cpp : 쉬운 계단 수

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

---

• 재귀호출로 각 자릿수에서 가능한 다음 위치들을 계산해나가면 아주 간단하게 풀 수 있지만, 시간초과가 난다.
• n 번째 자릿수에 들어갈 수 있는 값들은 n-1 번째 자릿수에 의해 결정된다. (0 과 9 의 경우는 1개씩, 나머지는 2개씩)
• 각 자릿수별로 가능한 숫자들을 저장할 배열을 만들어, 첫 자릿수부터 채우며 다음 자릿수를 결정한다.

---

#include <iostream>

using namespace std;

int n;
unsigned long long answer;
unsigned long long data[2][10];                     // 10개의 열은, 0~9 까지 각각 몇개의 숫자가 가능한지 담아놓음

int main(void)
{
    cin >> n;
    for(int i = 1 ; i <= 9 ; i++)                   // 0 으로 시작할 수 없기 때문에 1~9 까지만 가능한 숫자
    {
        data[1][i] = 1;
    }
    for(int digit = 2 ; digit <= n ; digit++)       // n 의 자리까지 
    {
        data[digit%2][0] = data[(digit+1)%2][1];    // 0 는 직전 자릿수의 +1 위치 (1) 의 값만을 더함
        data[digit%2][9] = data[(digit+1)%2][8];    // 9 는 직전 자릿수의 -1 위치 (8) 의 값만을 더함
        for(int i = 1 ; i <= 8 ; i++)               // 1~8 까지는 직전 자릿수의 (-1/+1) 위치의 값들을 더함
        {
            data[digit%2][i] = (data[(digit+1)%2][i-1] + data[(digit+1)%2][i+1]) % 1000000000;
        }
    }
    for(int i = 0 ; i <= 9 ; i++)
    {
        answer = (answer + data[n%2][i]) % 1000000000;  // 해당 자릿수에서 가능한 숫자의 갯수들을 모두 더함
    }
    cout << answer << endl;
}