[백준 25421번] 조건에 맞는 정수의 개수 (C++)

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

25421번: 조건에 맞는 정수의 개수

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N;
ll dp[10][100001], result; //정수, 자릿수

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N;

    for(int i=1; i<=9; i++) dp[i][1] = 1;

    for(int i=2; i<=N; i++) //자릿수
    {
        for(int j=1; j<=9; j++) //숫자
        {
            for(int k=-2; k<=2; k++) //이웃 숫자 조건
            {
                if(j+k < 1 || j+k > 9) continue;
                dp[j][i] += (dp[j+k][i-1]%MAX); 
            }
        }
    }

    for(int i=1; i<=9; i++) result += dp[i][N];

    cout << result % MAX;
    return 0;
}

 

자릿수가 1인 경우는 경우의 수가 1개밖에 존재하지 않는다. (1~9)

따라서 해당 케이스에 따른 dp 식을 1로 초기화 해준다. (dp[i][1] = 1)

 

이후 자릿수, 현재 숫자, 숫자에 대한 이웃 숫자 조건을 체크하여 dp 식을 갱신한다.

자릿수는 1의 경우 이미 초기화 했으므로 2부터 ~ 9까지,

숫자는 문제에 주어진 범위 대로 1~9까지,

이웃 숫자 조건은 문제에 주어진 조건 대로 현재 숫자 기준 -2 ~ 2까지이다.

 

현재 숫자가 j이고, 범위 조건을 탐색하는 인덱스가 k이다.

따라서 j+k가 최종 현재 숫자가 된다.

이 j+k가 1보다 작거나 9보다 크면 기존 최소 ~ 최대 숫자 범위를 벗어나는 것이므로 이런 경우에 예외처리가 필요하다.

이후 현 dp[숫자][자릿수]에 dp[범위내 이동 숫자][직전 자릿수]를 더해주며 dp식을 갱신해주면 된다.

 

이렇게 구한 값을 N자릿수에 대해서만 따로 누적합을 구하여 출력해주되 이때 987654321로 나눠주고 출력해준다.

평소에 저 숫자를 최소값 비교를 위한 최대값 MAX로 두고 설정해서 사용해왔기 때문에 선언했던 MAX를 그대로 사용해주었다.