[BOJ 10844번/C++] 쉬운 계단 수

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

10844번: 쉬운 계단 수

쉬운 계단 수

문제

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

 

제한사항

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

풀이

항상 DP문제는 규칙찾기 싸움이다..

 

N = 1일 때를 보자. 나올 수 있는 수로는

[ 1, 2, 3, 4, 5, 6, 7, 8, 9 ] 가 있다.

문제에서 0으로 시작되는 수는 없다고 명시되어있기 때문에 0은 포함되지 않는다. 그래서 총 9가지가 있다.

 

N = 2일 때는 다음과 같은 수들이 있다.

[ 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98 ]

총 17가지이다.

 

N = 2가 될 때 N = 1인 수들에서 어떤 변화가 있었는지를 살펴보자.

 

1이었던 수의 뒤에는 0과 2라는 수가 붙었다.

2였던 수의 뒤에는 1과 2이라는 수가 붙었다.

이 규칙이 8까지 모두 적용되었다.

 

즉, 1에서부터 8까지의 모든 수에는 그 수에서 ±1한 값들이 뒤에 붙었다.

 

마지막, 9의 뒤에는 8이 붙었다. 0이 올 수 없는 것에 유의하자.

이 말을 보고나면 0의 뒤에는 9가 아닌 1이 온다는 점을 알 수 있다. 0과 9의 차이는 1칸 차이가 아닌, 9의 차이이기 때문이다.

 

그래서 다음과 같은 규칙을 찾을 수 있다.

 

1. 앞에서 끝의 수가 0일 경우

뒤에는 항상 1이 붙게 된다.

 

2. 앞에서 끝의 수가 9일 경우

뒤에는 항상 8이 붙게 된다.

 

3. 1~8로 끝나는 경우

뒤에는 항상 ±1한 값이 붙게 된다.

 

이 규칙을 통해 다음과 같은 점화식을 만들 수 있다. 식의 값에는 실제 계단 수가 아닌 계단 수의 개수가 들어간다.

 

DP[길이가 N인 계단 수][끝이 0인 수] = DP[길이가 N-1인 계단 수][끝이 1인 수]

DP[길이가 N인 계단 수][끝이 9인 수] = DP[길이가 N-1인 계단 수][끝이 8인 수]DP[길이가 N인 계단 수][끝이 i인 수] = DP[길이가 N-1인 계단 수][끝이 i±1인 수]

 

이 식을 계산할 때 유의해야할 점으로 수가 매우 커질 수 있으므로 10억을 나눈 나머지를 출력하라고 되어있다.이에 조심하면서 코드를 작성하면 결과가 성공적으로 도출된다.

 

#include <iostream>

using namespace std;

long long dp[101][10];
const long long mod = 1000000000;

int main() {
    int N;
    fill_n(dp[1], 10, 1ll);
    cin >> N;
    dp[1][0] = 0ll;
    long long answer = 0ll;

    for (int i = 2; i <= N; i++) {
        for (int j = 0; j < 10; j++) {
            if (j == 0) {
                dp[i][j] = (dp[i - 1][j + 1]) % mod;
            }
            else if (j == 9) {
                dp[i][j] = (dp[i - 1][j - 1]) % mod;
            }
            else {
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod;
            }
        }
    }

    for (int i = 0; i < 10; i++) {
        answer += dp[N][i];
    }
    answer %= mod;

    cout << answer << endl;
    return 0;
}