[BOJ 25049] 백준 25049번 - 뮤직 플레이리스트

		2022 DGIST 현풍전산배 알고리즘 대회 풀이
A		[BOJ 25044] 에어컨
B		[BOJ 25045] 비즈마켓
C		[BOJ 25046] 사각형 게임 (Small)
D		[BOJ 25047] 사각형 게임 (Large)
E		[BOJ 25048] 랜선 연결
F		[BOJ 25049] 뮤직 플레이리스트

1. 문제

$25049$. 뮤직 플레이리스트 (2022 DGIST 현풍전산배 알고리즘 대회 F번)

백준 25049번 - 뮤직 플레이리스트 (https://www.acmicpc.net/problem/25049)

2. 풀이

1. 최대 두 번 현재 듣고 있는 곡보다 플레이리스트 상에서 앞에 위치했던 곡으로 돌아가 그 곡부터 다시 듣는다.
2. 같은 노래를 세 번 이상 듣게 되는 경우는 없도록 한다.

위 두 사실을 조합하면, 전체 합에 어떤 $i\sim j(1\leq i,j\leq N)$ 구간의 합을 최대 두 번 더하되, 각 구간이 겹쳐서는 안 된다는 조건으로 만들 수 있다. 즉, 최대 2개의 겹치지 않는 부분합 총합의 최댓값을 찾는 작업이 필요해진다. 부분합의 최댓값을 구하는 dp 문제로 결론지을 수 있다.

예제 입력 2의 예시를 예로 들어보면 다음과 같다.

7
-1 2 3 -8 6 -2 5

최대 두 개의 부분합의 총합의 최댓값이 그림과 같이 14이고 전체 합이 5이므로, 정답이 19가 된다.

---

그냥 처음부터 각 구간까지에 대해서 부분합을 구한 후, 최댓값을 순서대로 두 개 이하로 고르면 될 것 같기도 하다. 하지만, 이는 다음 예시에서 오류를 발생한다.

3
4 -1 3

부분합 dp 공식은 다음과 같다.

dp[i] = max(dp[i - 1] + P[i], P[i]);

이를 적용하면 각각의 구간에서 부분합은 $4,\;3,\;6$이 된다. 여기서 최댓값을 고르면 6을 고르고 종료하게 되는데(6은 전체 구간을 포함하므로 더이상 고를 수 없다), 실제 정답은 3과 4 두 구간을 더한 7이다. 따라서, 이 논리로는 모든 예제를 성공시킬 수 없다.

---

두 부분합 구간은 겹치지 않아야 한다. 따라서 기준점 $t$를 설정해서 왼쪽($1\sim t$)과 오른쪽($t+1\sim N$) 구간을 나누고, 각각의 구간에서 부분합의 최댓값을 찾는 방법을 생각해볼 수 있다.

기준점을 기준으로 왼쪽 구간($1\sim t$)은 $\rightarrow$ 방향으로 dp를 계산하고, 오른쪽 구간($t+1\sim N$)은 $\leftarrow$ 방향으로 dp를 계산한다. 그리고 각 구간에서의 dp[i]의 최댓값을 더하면, 해당 기준점에서의 부분합 총합의 최댓값을 구할 수 있다. 이를 모든 기준점에 대해서 수행해야 정답을 구할 수 있다.

연산 과정을 줄이기 위해, $\rightarrow$ 방향으로 전체 idx에 대해 dp값을 전부 구하고(Ldp), $\leftarrow$ 방향으로 전체 idx에 대해 dp값을 전부 구한다(Rdp). 그리고 Ldp의 구간별 최댓값, Rdp의 구간별 최댓값도 새로운 배열에 각각 계산하여 담는다. 이렇게 미리 처리해놓으면, 기준점을 설정했을 때 $O(N)$으로 최댓값을 갱신할 수 있다.

---

$t=0$인 경우와 $t=N$인 경우는 전체에 대해서 최대 부분합 구간을 하나만 찾는 과정이라고 간주할 수 있으므로, 따로 부분합 구간이 하나인 경우를 구할 필요는 없다.

이렇게 구한 부분합의 총합이 0보다 작을 경우는 부분합을 더하면 안 된다. 이는 되돌아가는 작업을 한 번도 하지 않는다는 것을 의미한다.

3. 채점 결과

4. 회고

.

5. 코드