백준 10844 - 쉬운 계단 수 [C/C++]

10844번: 쉬운 계단 수 (acmicpc.net)

10844번: 쉬운 계단 수

문제 설명은 다음과 같다.

문제 설명 / 입력 / 출력

예제 입력 / 예제 출력

 

처음에는 BFS로 풀려고 했는데, 풀다보니 시간초과가 날 게 너무 뻔해서 DP로 방향을 돌렸다.

 

내가 생각한 알고리즘은 다음과 같다.

• 우선 길이가 100인 숫자는 오버플로우가 날 수 밖에 없으니, int로 접근하면 안된다.
• 길이가 n인 숫자는, 길이가 n-1인 숫자에 뒤에 0~9를 붙인 것과 동치이다.
• 길이가 n인  숫자에서 일의 자리에 숫자 i가 붙은 경우, 이는 길이가 n-1인 숫자 중 일의 자리가 i-1과 i+1인 경우의 수를 더한 값과 같다.
• 위의 생각을 DP로 그대로 구현하면 끝!

아래는 제출한 C++ 코드이다. 

 

중요한 점은, 9에서 1을 더하면 0이 아니라 continue 시켜서 반복문을 넘겨야 하고, 0에서 1을 뺀 경우도 존재할 수 없으므로 반복문을 넘겨야 한다.

 

#include <iostream>
#include <algorithm>
#include <queue>
#define fastcpp ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
int n;
int dp[101][11];
int main() {
    fastcpp;

    cin >> n;
    for (int i=1;i<=9;i++) dp[1][i] = 1;
    dp[1][10] = 9;
    dp[1][0] = 0;
    for (int i=2;i<=100;i++){
        int V = 0;
        for (int j=0;j<=9;j++){
            if (j-1>=0) {
                V = (V + dp[i-1][j-1])%1000000000;
                dp[i][j] = (dp[i][j]+dp[i-1][j-1])%1000000000;
            }
            if (j+1<=9) {
                V = (V + dp[i-1][j+1])%1000000000;
                dp[i][j] = (dp[i][j]+dp[i-1][j+1])%1000000000;
            }
        }
        dp[i][10] = V;
    }
    cout << dp[n][10];
    return 0;

}