백준 10844 - 쉬운 계단 수

문제

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

10844번: 쉬운 계단 수

 

풀이

N자리 수의 마지막 자리, 즉 1의 자리에는 0부터 9까지 올 수 있다. 이때 0과 9를 제외한 1부터 8까지는 앞 자리에 각각 2개의 수가 올 수 있다. 

 

예를 들어, 

○ ○ ○ ◎ ● 의 5자리 수가 있고 ●가 1이면 ◎에는 0, 2 이렇게 두 개가 올 수 있다.

하지만 ●가 0이면 ◎에는 1만 올 수 있다. 마찬가지로 ●이 9여도 앞에 자리에는 8만 올 수 있다. 

 

D[N][L] = N자리에 오는 마지막 수 L 이라고 하면 다음과 같은 점화식을 만들 수 있다.

D[N][L] = {

    D[N][L] = D[N-1][L-1] + D[N-1][L+1] (L이 1~8일때)

    D[N][L] = D[N-1][L+1] (L이 0일때)

    D[N][L] = D[N-1][L-1] (L이 9일때)

}

 

세 개의 경우를 더하면 N일때 나오는 계단 수의 갯수를 구할 수 있다.

 

코드

탑다운 방식

#include <iostream>
 
using namespace std;
 
int N;
int dp[101][10];
int result;
 
const int mod = 1000000000;
 
int f(int N, int L)
{
    if (N == 1) return L == 0 ? 0 : 1;
    if (dp[N][L]) return dp[N][L];
    if (L == 0) return dp[N][L] = f(N - 1, 1) % mod;
    if (L == 9) return dp[N][L] = f(N - 1, 8) % mod;
 
    return dp[N][L] = (f(N - 1, L + 1) + f(N - 1, L - 1)) % mod;
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> N;
 
    for (int i = 0; i < 10; i++)
        result = (result + f(N, i)) % mod;
 
    cout << result;
 
    return 0;
}

 

바텀업 방식

#include <iostream>
 
using namespace std;
 
int N;
int dp[101][10];
int result;
 
const int mod = 1000000000;
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> N;
 
    for (int i = 1; i < 10; i++) dp[1][i] = 1;
    for (int i = 2; i <= N; i++)
    {
        for (int j = 0; j < 10; 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]) % mod;
        }
    }
 
    for (int i = 0; i < 10; i++) result = (result + dp[N][i]) % mod;
 
    cout << result;
 
    return 0;
}