백준 1462: 퀴즈쇼

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

 

이 문제는 예전에 해결한 문제지만, DP에 대한 시간복잡도를 고려하지 않았던 나에게 있어 좋았던 문제여서 이렇게 다뤄보려 한다.

 

이 문제의 첫 인상은 답답함이다. N이 최대 500,000이라서 그리디적으로 해결해야 할지 고민을 할 정도였다. 하지만 천천히 읽어보니 DP 사용이 적합해보였다. 처음 생각한 점화식은 다음과 같다.

 

DP[idx][cnt] = max(DP[idx + 1][(cnt + 1 == M ? 0 : cnt + 1)] + score[idx] + (cnt + 1 == M ? bonusScore[idx] : 0)

, dp[idx + 1][cnt])

 

하지만 처음에 얘기한 듯 이 문제의 N이 너무 커서 이런 점화식을 잡으면 500,000 * 500,000 의 메모리를 잡아먹어서, 메모리 초과란 결과를 얻는 것은 불보듯 뻔한 결과다. 그래서 나는 1차원 DP로 어떻게 문제를 해결할 지 고민하였고, 겨우 해결책을 떠올렸다. DP에서 cnt를 빼고, 하나의 점화식을 통해 M개의 반복문을 돌리는 것이다. 이러면 1차원 DP로도 충분히 해결할 수 있다고 생각했고, 바로 코드를 구성하였다.

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
using ll = long long;
int N, M;
ll S[500001], B[500001], dp[500001];
ll solve(int idx)
{
	if (idx >= N) return 0;
	ll& ret = dp[idx];
	if (ret >= 0) return ret;
	int s = 0;
	for (int i = idx; i < min(N, idx + M); i++)
	{
		if (i == idx + M - 1) ret = max(ret, solve(i + 1) + s + B[i] + S[i]);
		ret = max(ret, solve(i + 1) + s - S[i]);
		s += S[i];
	}
	return ret;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	memset(dp, -1, sizeof(dp));
	cin >> N >> M;
	for (int i = 0; i < N; i++) cin >> S[i];
	for (int i = 0; i < N; i++) cin >> B[i];
	cout << solve(0) << '\n';
}

이 해결방식을 택했을 때는 정말 옳거니하고, 이게 정답일 것이라 생각했다. 결과는 "시간 초과"이다. 나는 이해할 수가 없었다. 분명 이것보다 더 좋은 해결방식이 없을텐데 도대체 왜 "시간 초과"가 나는지 도저히 알 수가 없었다.

 

혹시 누적 합이 필요한가? 아니면 남은 퀴즈 갯수가 N개 이하면 나머지를 다 더하는 그리디적 발상이 필요한가? 이러한 생각을 안고 코드를 수정하였지만.

#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
int N, M;
const ll INF = -100000000000000;
ll S[500003], B[500003], dp[500003], acc[500003];
ll solve(int idx)
{
	if (idx > N) return 0;
	ll& ret = dp[idx];
	if (ret > INF) return ret;
	for (int i = idx; i <= min(N, idx + M - 1); i++) ret = max(ret, solve(i + 1) + acc[i - 1] - acc[idx - 1] - S[i]);
	return ret;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	acc[0] = 0;
	for (int i = 1; i <= N; i++)
	{
		cin >> S[i];
		acc[i] = acc[i - 1] + S[i]; // 누적 합 추가
		dp[i] = INF;
	}
	for (int i = 1; i <= N; i++) cin >> B[i];
	cout << solve(1) << '\n';
}

결과는 모두 "시간 초과"이다. 결국 나는 이 문제를 포기하고, 다른 문제를 해결하러 갔다.

 

시간이 지나고, 다시 이 문제를 생각하니 "시간 초과"가 날 수 밖에 없었다란 생각이 들었다. 아무리 DP를 사용한다고 해도, 이 문제는 for문을 M번 돈다. 재귀를 N번 돈다고 한다면 이 코드의 시간복잡도는 O(N * M), 즉 500,000 * 500,000 만큼 시간이 걸린다. 다시말하면 공간복잡도가 시간복잡도로 옮겨간 격이다. 이래서는 처음 아이디어와 별 다를 바가 없다.

 

그러면 해결책을 무엇일까? 위 코드의 문제점을 보았을 때, 가짓수가 너무 많은 것이 문제다. 1~M까지 푼 갯수를 일일히 가다보니 "시간 초과"가 난 것이다. 그렇다면 가짓수를 줄일 수 없을까란 생각이 들었다. 처음부터 경우의 수를 고려하며 문제 해결에 집중을 해보았고, 가짓수를 줄일 방법이 떠올랐다.

 

처음으로 돌아가는 것이 키워드였다. 보너스 점수에 휘둘리다 보니 문제 해결에 실마리가 보이지 않았던 것이다. 이 문제의 가짓수는 다음과 같이 나눌 수 있다.

 

1. 문제를 해결

2. 문제를 틀림

3. 문제를 M개 연속으로 맞추고, 보너스 점수를 얻음.

 

여기서 3번은 조건이 붙는다. 1번을 연속으로 해결하다가 3번을 고르면 안되기에, 2번을 하고 나서 3번을 할 수 있다는 제약을 걸어야한다. 즉, dp를 2차원으로 바꿔서 이전에 2번을 골랐는지 확인을 하면 된다.

 

이런 의문이 들 수 있는데, 1번만하는 것이 답으로 나오면 어떡하냐? 는 것인데, 이 경우는 보너스 점수를 얻는 것이 이득이라서 그리디적인 이론에 의해 있을 수 없다고 생각을 했다.

#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
int N, M;
const ll INF = -100000000000000;
ll S[500003], B[500003], dp[500003][2], acc[500003];
ll solve(int idx, bool bonus)
{
	if (idx > N) return 0;
	ll& ret = dp[idx][bonus];
	if (ret > INF) return ret;
	ret = 0;
    // 3번 케이스
	if (bonus && idx + M - 1 <= N) 
    	ret = max(ret, solve(idx + M, true) + acc[idx + M - 1] - acc[idx - 1] + B[idx + M - 1]);
    // 1번 케이스
	ret = max(ret, solve(idx + 1, false) + S[idx]);
    // 2번 케이스
	ret = max(ret, solve(idx + 1, true) - S[idx]);
    
	return ret;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	acc[0] = 0;
	for (int i = 1; i <= N; i++)
	{
		cin >> S[i];
		acc[i] = acc[i - 1] + S[i];
		dp[i][0] = dp[i][1] = INF;
	}
	for (int i = 1; i <= N; i++) cin >> B[i];
	cout << solve(1, true) << '\n';
}

3번은 부분합을 이용해서 시간을 절약하였다.

 

이 문제를 처음 풀기 시작하고 4개월만에 해결해서 묵은 때가 한 번에 날아간 듯했다.