취미로 코딩하기

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

이번에 볼 문제는 백준 25049번 문제인 뮤직 플레이리스트이다.
문제는 아래 링크를 확인하자.

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

문제에서 구하는 값을 식으로 정리하면 (전체 곡의 Pi의 합) + ([L1,R1] 곡의 Pi의 합) + ([L2,R2] 곡의 Pi의 합)과 같이 나타낼 수 있다. (단, 두 구간은 겹치지 않고, 각 구간은 공집합이 될 수 있다.)

위의 두 구간은 겹치지 않으므로 어떤 인덱스 i에 대하여 [L1,R1]은 [0,i]에 속하고 [L2,R2]는 [i+1,N+1]에 속하게 하는 i는 항상 존재한다. (단, P0 = P(N+1) = 0으로 정의한다) 따라서 각 i에 대해 [0,i]와 [i,N+1] 각 구간에 대해 maximum subarray를 미리 찾아두는 것으로 문제를 해결할 수 있다. 이는 Kadane's algorithm을 활용해 쉽게 계산해낼 수 있다.

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

#include <iostream>
using namespace std;
typedef long long ll;

int N;
ll arr[500002];
ll dpL[500002], dpR[500002];
ll total;

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

	cin >> N;
	for (int i = 1; i <= N; i++) {
		ll& tmp = arr[i];
		cin >> tmp;
		total += tmp;
	}
	for (int i = 1; i <= N; i++) dpL[i] = max(0LL, dpL[i - 1] + arr[i]);
	for (int i = 1; i <= N; i++) dpL[i] = max(dpL[i - 1], dpL[i]);
	for (int i = N; i > 0; i--) dpR[i] = max(0LL, dpR[i + 1] + arr[i]);
	for (int i = N; i > 0; i--) dpR[i] = max(dpR[i + 1], dpR[i]);

	ll ans = 0;
	for (int i = 0; i <= N; i++) ans = max(ans, dpL[i] + dpR[i + 1]);
	cout << total + ans;
}