Sean’s Dlog
Sean’s Dlog/
[백준] 10844번 - 쉬운 계단 수
Search
[백준] 10844번 - 쉬운 계단 수

[백준] 10844번 - 쉬운 계단 수

Tags
Coding Test
www.acmicpc.net
https://www.acmicpc.net/problem/10844

문제

💡
45656이란 수를 보자.
이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.
시간 제한: 1초
메모리 제한: 256MB

입력

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

출력

💡
첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.
예제 입력
예제 출력
1
9
2
17

풀이

앞자리가 x인 n자리 계단수를 DP table로 정리하면 다음과 같이 채울 수 있다.
ㅤ
0
1
2
3
4
5
0
0
1
1
2
3
6
1
1
1
2
3
6
10
2
0
1
2
4
7
14
3
0
1
2
4
8
15
4
0
1
2
4
8
16
5
0
1
2
4
8
16
6
0
1
2
4
8
15
7
0
1
2
4
7
14
8
0
1
2
3
6
10
9
0
1
1
2
3
6
+
0
9
17
32
61
116
위 표를 보고 dp의 점화식을 구해보면 dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] 이 나온다. 그러나 항상 점화식과 같지는 않다. [1, x]와 [n,0], [n, 9]의 경우는 점화식과 다른 규칙을 갖고 있어 다른 규칙을 적용해야한다.
이전 원소를 채워야 다음 원소를 구할 수 있으므로 바텀업 방식을 사용했다. 이후 모듈러 연산을 적용했다.

코드

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
const int M = 1000000000;
int main() {
    int n;
    cin >> n;
    vector<vector<long long>> dp(n + 1, vector<long long>(10, 0));

    for (int i = 0; i < 10; ++i) {
        dp[1][i] = 1;
    }
    dp[0][1] = 1;

    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] % M;
            } else if (j == 9) {
                dp[i][j] = dp[i - 1][j - 1] % M;
            } else {
                dp[i][j] = (dp[i - 1][j - 1]% M + dp[i - 1][j + 1] % M) % M;
            }
        }
    }

    long long ans = accumulate(dp[n].begin() + 1, dp[n].end(), 0LL) % M;
    cout << ans;
    return 0;
}
모듈러 계산 결과값이 커서 long long 자료형을 사용했고, 이에 따라 accumulate함수의 마지막 매개변수를 0LL으로 수정했다.
Copyright 2025 SeanM