백준 25421 조건에 맞는 정수의 개수 (c++) : 피너클

https://www.acmicpc.net/problem/25421

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

다이나믹 문제다.

탑다운으로 풀려고 했지만 함수 호출량이 너무 많은거 같아 바텀업으로 풀게됬다.

int n;
long long dp[10][100001];
long long MOD = 987654321;

사용할 변수다.

cin >> n;
memset(dp, 0, sizeof(dp));
long long ans = 0;
for (int i = 1; i <= 9; i++) {
    dp[i][1] = 1;
}

값을 입력받고 dp를 0으로 초기화한뒤 dp[i][1] = 1로 바꾼다.

dp[9][10]은 10의 자릿수에서 10이 나온 횟수를 의미한다.

dp[1][1]이라면 1의 자릿수에서 1이 나온 횟수니 1이 된다.

for (int i = 2; i <= n; i++) {
    for (int j = 1; j <= 9; j++) {
        for (int k = -2; k <= 2; k++) {
            if (1 <= j + k && j + k <= 9) {
                dp[j][i] += dp[j + k][i - 1];
                dp[j][i] %= MOD;
            }
        }
    }
}

그후 n의 자릿수까지 1부터 9까지 하나 하나 확인하며 나아간다.

만약 j + k가 범위 안에 있다면 dp[j][i]에 dp[j + k][i - 1]을 더하고 MOD로 나눈다.

for (int i = 1; i <= 9; i++) ans = (ans + dp[i][n]) % MOD;

cout << ans << endl;

그후 ans에 하나씩 더하고 MOD로 나눈뒤 출력하면 된다.

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int n;
long long dp[10][100001];
long long MOD = 987654321;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	memset(dp, 0, sizeof(dp));
	long long ans = 0;
	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 (1 <= j + k && j + k <= 9) {
					dp[j][i] += dp[j + k][i - 1];
					dp[j][i] %= MOD;
				}
			}
		}
	}
	for (int i = 1; i <= 9; i++) ans = (ans + dp[i][n]) % MOD;

	cout << ans << endl;
}

전체코드다.