[BOJ 25199 // C++] 도박사 곰곰

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 25199번 문제인 도박사 곰곰이다.
문제는 아래 링크를 확인하자.

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

25199번: 도박사 곰곰

dp[m][n]을 (1 이상 m 이하의 수가 적힌 카드를 n장 뽑은, 지는 상태의 경우의 수)라 정의하면 다음과 같은 식이 성립한다.

 

dp[m][n] = (dp[m-1][n - (카드 m을 최대로 뽑아도 되는 장수)] ~ dp[m-1][n])의 합

 

위와 같은 합의 형태는 매번 하나하나 더해 값을 구하기보다는 prefix sum 전처리를 통해 시간복잡도를 개선할 수 있다.

 

위와 같은 방식으로 구현하면 답을 O(MN)에 계산해낼 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int arr[1001];
int dp[1001][1001];
int psum[1001];

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

	int cnt = 0, cntx = 0;
	int N, M; cin >> N >> M;
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		arr[x]++;
		if (arr[x] > cnt || (arr[x] == cnt && cntx < x)) cnt = arr[x], cntx = x;
	}

	dp[0][0] = 1;
	for (int n = 1; n <= M; n++) {
		int c;
		if (n < cntx) c = cnt;
		else c = cnt - 1;
		psum[0] = 1, dp[n][0] = 1;
		for (int k = 1; k <= N; k++) {
			psum[k] = psum[k - 1] + dp[n - 1][k];
			if (psum[k] > 1000000006) psum[k] -= 1000000007;

			if (k > c) {
				dp[n][k] = psum[k] - psum[k - c - 1];
				if (dp[n][k] < 0) dp[n][k] += 1000000007;
			}
			else dp[n][k] = psum[k];
		}
	}

	cout << dp[M][N];
}