글 읽기 - 제가 푼 방식도 동적 계획법인가요...?

hnduddn 2년 전 0

경우의 수 따지다 보니 자리 수 증가 할 때마다 n 과 n-1 자리의 숫자 경우의 수가 규칙적으로 늘어나는게 보이길래 arr 배열에 갱신되게 했는데

다른분들 풀이랑 다르네요....

#include <iostream>
using namespace std;

int dp[1002] = { 0, 10, 55};
int arr[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

int main() {
	int n; 

	cin >> n;

	for (int i = 3; i <= n; i++) {
		int sum = 0;
		int sub = 0;
		for (int j = 0; j < 10; j++) {
			if (dp[i - 1] > 1000000000) {
				int temp = arr[j] % 10007;
				arr[j] = (dp[i - 1] % 10007) - (sub % 10007);
				sub += temp % 10007;
				sum += arr[j] % 10007;
			}
			else {
				int temp = arr[j] % 10007;
				arr[j] = dp[i - 1] - sub;
				sub += temp % 10007;
				sum += arr[j] % 10007;
			}
		}
		dp[i] = sum;
	}

	cout << dp[n] % 10007;
}

herdson 2년 전 1

코드로 보아 dp 배열을 2개 쓰신 셈이 되는데 dp 배열을 2개 써서 푸는 문제도 많이 있습니다.

좋은 접근이라 봅니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

제가 푼 방식도 동적 계획법인가요...?

hnduddn 2년 전 0

herdson 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말