(백준 / DP) 200년간 폐관수련했더니 PS 최강자가 된 건에 대하여

문제 요약

• 순서대로 대회에 참여해 상금을 타려 한다.
• n-1번 대회에 참여하면서 얻은 상금 합이 n번 대회 제한을 넘어서면 참가할 수 없다.
• N개의 대회중 N-1개의 대회에 참여할 수 있는지 확인하라
• N < \(10^6\), 대회 상금, 대회 상금제한 < \(10^9\)

원문

솔루션

대회의 수가 최대 100,000 이므로, 대회 참석 여부를 0과 1로 이루어진 수열로 나타내면 경우의 수는 \(2^{100000}\)

일반적인 메모이제이션으로 접근할 수 있는 수치가 아니다.

문제에서 요구하는 값은 N개의 대회 중 N-1개의 대회에 참가할 수 있는지 이다. N-1번째 대회 결과에 따라 N번째 대회 참석 가능 여부가 결정되는 선형적인 상태를 가지고 있으므로 점화식을 세워 볼 수 있다.

상태공간

N-1번째 대회를 마치고 N번 대회에 참석했을 때 가능한 상태는 두 가지이다.

1. N번 대회까지 한번도 대회를 빠지지 않을 때 얻은 상금.

2. N번 대회 이전까지 딱 한번 빠졌을 때 얻은 상금.

N번 대회에서 가능한 선택지는 세 가지이다.

**1. 이전까지 대회를 모두 참석했고, 이번에도 참석한다. **

2. 이전까지 한번도 대회를 빠지지 않았지만, 이번 대회에서는 빠진다.

**3. 이전에 한번 빠졌지만, 이번 대회는 참석한다 **

선택지 1번의 결과는 상태 1번의 값이 되고 선택지 2, 3번의 결과는 상태 2가 된다.

시간복잡도

\(10^{6}_{대회개수}\)

코드

 #include <iostream>
using namespace std;
/*
* ARR : 대회 참여 제한 점수와 점수 입력받는 변수
* DP[0] : 이전 대회 참여 이력
* DP[1] : 현재 대회 참여 결과
*/
int N, ARR[111111][2] = { 0, };
long long int DP[2][2] = { 0, };
int main() {
	int i, j;
	cin >> N;
	for (i = 1; i <= N; i++) {
		for (j = 0; j < 2; j++)cin >> ARR[i][j];
	}
	//cout << endl;
	for (i = 1; i <= N; i++) {
		int limit = ARR[i][0];
		int score = ARR[i][1];

		//1-1 대회를 다 참여한 경우
		DP[1][0] = (DP[0][0] <= limit) ? DP[0][0] + score : 1e16;

		//2-1 대회를 다 참여하지 않은 경우

		long long int ret1 = 0, ret2 = 0;
		//2-2-1 이전 대회를 다 참여하고 이번에 참여하지 않는 경우
		ret1 = (DP[0][0]) ? DP[0][0]: 1e16;

		//2-2-2 이미 이전에 한번 대회를 참여하지 않은 경우
		ret2 = (DP[0][1] <= limit) ? DP[0][1] + score : 1e16;
		DP[1][1] = (ret1 < ret2) ? ret1 : ret2;

		if (DP[1][0] == 1e16 && DP[1][1] == 1e16) {
			cout << "Zzz" << "\n";
			return 0;
		}

		DP[0][0] = DP[1][0];
		DP[0][1] = DP[1][1];
		cout << DP[0][0] << " " << DP[0][1] << " " << ret1 <<" " <<  ret2 <<  "\n";
	}
	cout << "Kkeo-eok" << "\n";
}