[백준] 10844 C++ 쉬운 계단 수 (DP)

- 문제 설명

 

- 문제 풀이

처음에 문제 설명을 볼때 문제 자체를 이해하는데 은근 오래 걸렸다.

간단하게 설명해서, 길이가 1이면 1, 2, 3, 4, 5, 6, 7, 8, 9 로 9개 있다.(0으로 시작하는건 제외)

길이가 2이면 10, 21, 12, 32, 23, 43, 34, 54, 45, 65, 56, 76, 67, 87, 78, 98, 89로 총 17개가 있다.

 

여기서 중요하게 봐야할 점은 첫째 자리 수이다. 보면 0부터 시작해서 9로 끝나는 첫 째 자리 수를 순서대로 나열했는데, 이를 이용해 2차원 배열을 만들 수 있다. 길이 by 첫 째 자릿 수로 배열을 만들면 길이가 N이라고 할때 배열의 크기는

DP[N][10] 이 된다. 이때 편의상 코드에서는 DP[N+1][10]으로 해두겠다.

 

아래 그림을 보면 점화식을 알 수 있다.

예를 들어 DP[2][1] 같은 경우엔 2의 길이를 가지고 첫 째 자릿 수가 1인 가짓 수 인데, 01은 시작값이 0이기 때문에 없고 21만 가능하다. 따라서 길이를 i, 첫 째 자릿수를 j라고 하면 DP[i][j] = DP[i-1][j-1] + DP[i-1][j+1]이 성립하게 된다. 즉 길이가 한칸 전에서의 +1, -1 한 뒷 자릿 수의 경우의 수를 더해준 값과 같다.

단, 여기서 첫 째 자릿수가 0일때와 9일 때는 -1, 10의 자릿수는 없기 때문에 예외로

0일 때 - DP[i][0] = DP[i-1][1]

9일 때 - DP[i][9] = DP[i-1][8]

이 성립하게 된다.

 

 

- 코드

#include  <iostream>
#define NUM 1000000000
using namespace std;

int N, result = 0;
int dp[101][10];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;
    for (int i = 1; i < 10; i++)
        dp[1][i] = 1;  // 자릿수가 한 자릿수 일땐 0일때 제외하고 전부 1

    for (int i = 2; i <= N; i++)
    {
        for (int j = 0; j < 10; j++)
        {
            if (j == 0)             // 첫째 자리 수가 0일때 자릿수가 -1인 수는 없으므로 [1]만 더함
                dp[i][j] = dp[i - 1][1];
            else if (j == 9)
                dp[i][j] = dp[i - 1][8]; // 첫째 자리 수가 9일때 자릿수가 10인 수는 없으므로 [8]만 더함
            else
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]; // 현재 첫째 자리 수에 전 단계의 자리수 +- 1 였던 값을 더함 
            dp[i][j] %= NUM;
        }
    }

    for (int i = 0; i < 10; i++)
    {
        result = (result + dp[N][i]) % NUM; // +=로 할 경우 연산 순서가 달라져서 (result + dp[N][i])로 해야함
    }

    cout << result;

    return 0;
}