백준 1562번 [계단 수](C++) -yes6686- 티스토리

백준 문제 풀이: 1562 [계단 수]

---

문제 링크: https://www.acmicpc.net/problem/1562

문제 설명:

길이가 N인 계단 수는, 각 자릿수가 0부터 9까지 한 번씩 모두 포함되고, 자릿수 차이가 ±1인 수를 의미합니다. 주어진 N에 대해 계단 수의 개수를 구하는 문제입니다.

---

문제 해결 코드

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

int dp[101][10][1 << 10];

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // 초기값 설정: 첫 자리는 1부터 9까지 가능
    for (int i = 1; i <= 9; i++) {
        dp[1][i][1 << i] = 1;
    }

    // DP 계산
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j <= 9; j++) {
            for (int t = 0; t < (1 << 10); t++) {
                if (j == 0) { // 현재 자릿수가 0일 때
                    dp[i][j][t | (1 << j)] = (dp[i][j][t | (1 << j)] + dp[i - 1][j + 1][t]) % mod;
                } else if (j == 9) { // 현재 자릿수가 9일 때
                    dp[i][j][t | (1 << j)] = (dp[i][j][t | (1 << j)] + dp[i - 1][j - 1][t]) % mod;
                } else { // 1 ≤ j ≤ 8
                    dp[i][j][t | (1 << j)] = (dp[i][j][t | (1 << j)] + dp[i - 1][j + 1][t]) % mod;
                    dp[i][j][t | (1 << j)] = (dp[i][j][t | (1 << j)] + dp[i - 1][j - 1][t]) % mod;
                }
            }
        }
    }

    // 결과 계산
    int ans = 0;
    for (int i = 0; i <= 9; i++) {
        ans = (ans + dp[n][i][(1 << 10) - 1]) % mod;
    }
    cout << ans;
}

예제

입력:
2

출력:
17

---

코드 설명

• DP 배열: dp[i][j][t]는 길이가 i이고, 마지막 자리가 j이며, 비트마스크 t가 나타내는 숫자 상태(0~9 중 포함 여부)를 만족하는 계단 수의 개수를 저장합니다.
• 초기화: 첫 자릿수(1부터 9까지)에 대해 비트마스크를 설정하여 초기화합니다.
• 점화식:
  • j = 0일 때, 이전 자릿수는 j+1만 가능합니다.
  • j = 9일 때, 이전 자릿수는 j-1만 가능합니다.
  • 1 ≤ j ≤ 8일 때, 이전 자릿수는 j±1 모두 가능합니다.
• 결과 계산: 길이가 N이고, 모든 숫자를 포함하는 비트마스크 (1 << 10) - 1에 대해 가능한 모든 dp 값을 더합니다.

시간 복잡도

• DP 계산: O(N × 10 × 1024)
• 모든 숫자를 포함하는 경우를 효율적으로 처리할 수 있습니다.

---

결과

주어진 조건에서 계단 수의 개수를 효율적으로 계산할 수 있습니다. 추가적인 테스트 케이스로 정확도를 확인할 수 있습니다.