[백준] 10844번 쉬운 계단 수

문제

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

풀이과정

D[i]를 길이가 i인 수의 계단수의 개수라고 생각해보고 풀려고 하다가 시간을 엄청 날려먹었다.

결국 검색을 통해 답을 보고 해결했다. D[i][j]를 길이가 i, 마지막 수가 j인 수의 계단수의 개수라고 생각하고 풀면 된다고 한다.

그러면 D[i][j] = D[i-1][j-1] + D[i-1][j+1] 이라는 식이 나온다고 말한다.

식만봐서는 이해하기 힘들어서 직접 길이가 3이고 마지막 수가 3인 경우를 생각해봤다.

D[3][3]은 직접 경우를 따져보니 123, 323, 343, 543 총 4개였다. 이렇게 직접해보니 위의 식이 이해가 됐다.

소스코드

#include <iostream>
 
using namespace std;
 
int N;
long long D[101][101];
long long mod = 1000000000;
 
int main()
{
    cin.sync_with_stdio(false);
 
    cin >> N;
 
    for (int i = 1; i <= 9; i++) D[1][i] = 1;
 
    for (int i = 2; i <= N; i++)
    {
        for (int j = 0; j <= 9; j++)
        {
            D[i][j] = 0;
 
            if (j-1 >= 0) D[i][j] += D[i - 1][j - 1];
            if (j + 1 <= 9) D[i][j] += D[i - 1][j + 1];
 
            D[i][j] %= mod;
        }
    }
 
    long long ans = 0;
    
    for (int i = 0; i <= 9; i++)
    {
        ans += D[N][i];
    }
 
    ans %= mod;
 
    cout << ans;
 
    return 0;
}