백준 10844 쉬운 계단 수

작성일 | In |

Problem : 쉬운 계단 수

유형 : DP

문제 설명

45656이란 수를 보자. 이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.
세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

예제 입력

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

1
1

예제 출력

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

1
9

해결 전략

계단수의 정의를 자세히 보면 다음과 같음을 추측 할 수 있다.

  • 두 자리의 수에서 첫번째의 숫자가 1이면
  • 두번째 숫자는 0 또는 2가 된다.
  • 만약 세 자리의 수에서 맨 첫번째의 숫자가 5이면
  • 두번째 숫자는 4 또는 6이 된다.

큰 문제를 작은 문제로 쪼개서, 해결할 수 있게 된다.

dp[n][m]
길이가 n , 첫번째 수가 m
인접한 수는 +- 1을 해서 찾을 수 있다

dp[n][m] = dp[n][m-1] + dp[n][m+1]

이때 , m-1이나 m+1이 0보다 작거나 9보다 클 수 없다.
예외처리 해준다.

주의할 점

  • 맨 앞의 수가 9일때,

  • 뒤에 나오는 수는 8만 가능하고 10은 불가능하다.

  • 맨 앞의 수가 0일때, 이 경우는 불가능하지만
    • 02는 불가능 하지만 구해놓아야 한다.
    • 102의 경우에 위에서 구해놓은 02를 이용 해야한다.
  • 뒤에 나오는 수는 1만 가능하고 -1은 불가능하다.

풀이

점화식을 세운다.

  • dp[n][m] 길이가 n , 첫번째 수가 m
  • dp[n] = dp[n][1~9]의 합

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll dp[101][10];
int n;

const int mod = 1000000000LL;

ll solve() {
    for (int i = 2; i <= n; ++i) {
        for (int ii = 0; ii <= 9; ++ii) {
            if (ii - 1 >= 0) dp[i][ii] += dp[i - 1][ii - 1];
            if (ii + 1 <= 9) dp[i][ii] += dp[i - 1][ii + 1];
            dp[i][ii] %= mod;
        }
    }
    ll answer = 0;
    for (int i = 1; i <= 9; ++i) {
        answer = (answer + dp[n][i])%mod;
    }
    return answer % mod;
}

ll input() {
    cin >> n;
    if (n == 1) return 9;

    for (int i = 0; i <= 9; ++i) dp[1][i] = 1;
    return solve();
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("input.txt", "r", stdin);
    cin.tie(NULL);  cout.tie(NULL);

    cout << input();

    return 0;
}

피드백

첫번째 숫자가 아닌, 마지막 숫자를 기준으로 풀이하는것도 괜찮은것 같다.