백준 25421번 [조건에 맞는 정수의 개수](C++) -yes6686- 티스토리

백준 문제 풀이: 25421 (조건에 맞는 정수의 개수)

---

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

문제 설명:

주어진 조건에 따라 길이 n의 정수를 만들 수 있는 경우의 수를 구합니다. 각 자리의 숫자는 **1~9**까지이며, 인접한 자리의 숫자 차이가 최대 **2 이하**여야 합니다. 결과를 **987654321**로 나눈 나머지를 출력합니다.

---

문제 해결 코드

#include <iostream>
#define MOD 987654321
using namespace std;

long long int arr[10];  // 현재 자리에서 가능한 숫자 개수
long long int carr[10]; // 이전 자리 숫자 개수를 복사할 배열

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // n이 1인 경우, 결과는 9 (1~9까지 가능)
    if (n == 1) {
        cout << 9;
        return 0;
    }

    // 초기 값 설정: 길이가 1일 때 각 숫자는 하나씩 존재
    for (int i = 1; i <= 9; i++) {
        arr[i] = 1;
    }

    long long int ans = 0;

    // n자리 숫자를 만들기 위한 DP
    for (int t = 2; t <= n; t++) {
        // 현재 배열 carr에 이전 자리 값을 복사
        for (int i = 1; i <= 9; i++) {
            carr[i] = arr[i] % MOD;
            arr[i] = 0; // arr 초기화
        }

        // DP 상태 전이
        for (int i = 1; i <= 9; i++) {
            if (i == 1) { // 숫자 1의 경우
                arr[i] += carr[i];
                arr[i + 1] += carr[i];
                arr[i + 2] += carr[i];
            } else if (i == 2) { // 숫자 2의 경우
                arr[i - 1] += carr[i];
                arr[i] += carr[i];
                arr[i + 1] += carr[i];
                arr[i + 2] += carr[i];
            } else if (i >= 3 && i <= 7) { // 중간 숫자들
                arr[i - 2] += carr[i];
                arr[i - 1] += carr[i];
                arr[i] += carr[i];
                arr[i + 1] += carr[i];
                arr[i + 2] += carr[i];
            } else if (i == 8) { // 숫자 8의 경우
                arr[i - 2] += carr[i];
                arr[i - 1] += carr[i];
                arr[i] += carr[i];
                arr[i + 1] += carr[i];
            } else { // 숫자 9의 경우
                arr[i - 2] += carr[i];
                arr[i - 1] += carr[i];
                arr[i] += carr[i];
            }
            arr[i] %= MOD; // MOD 연산
        }
    }

    // 최종 결과 계산
    for (int i = 1; i <= 9; i++) {
        ans += arr[i];
        ans %= MOD;
    }

    cout << ans;
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

• DP(동적 계획법): 각 숫자 1~9에 대해 이전 자리의 숫자에서 인접한 숫자로 이동이 가능한 경우를 누적해 나갑니다.
• 상태 전이: - arr[i]는 현재 자리에서 숫자 i로 끝나는 수의 개수를 의미합니다. - 숫자 i에 대해 이동 가능한 범위는 **i-2 ~ i+2**입니다.
• MOD 연산: 결과값이 매우 커질 수 있으므로 중간 단계에서 **MOD (987654321)**를 사용하여 나머지를 구합니다.

시간 복잡도 분석

• 자리 수 n에 대해 숫자 1~9를 순회하며 계산합니다.
• 시간 복잡도는 **O(n ⋅ 9)** = **O(9n)**으로 매우 효율적입니다.

---

결과

주어진 조건에 따라 길이 n의 정수를 만들 수 있는 경우의 수를 출력합니다.

• 입력 예시:

  2

• 출력 예시:

  17

• 입력 예시:

  3

• 출력 예시:

  49

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!