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

1. 문제Permalink

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

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

2. 풀이Permalink

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

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

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

7
-1 2 3 -8 6 -2 5

boj-25049

최대 두 개의 부분합의 총합의 최댓값이 그림과 같이 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를 설정해서 왼쪽(1t)과 오른쪽(t+1N) 구간을 나누고, 각각의 구간에서 부분합의 최댓값을 찾는 방법을 생각해볼 수 있다.

boj-25049

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

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


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

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

3. 채점 결과Permalink

boj-25049

4. 회고Permalink

.

5. 코드Permalink

#include <bits/stdc++.h>
using namespace std;
#define FASTIO cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long int
#define pii pair<int, int>
#define PQ priority_queue
#define LEN(v) int(v.size())
#define ALL(v) v.begin(),v.end()
#define INF 2e9
#define LINF 1e18
int main() {
FASTIO;
int N;
cin >> N;
vector<ll> P(N);
vector<ll> Ldp(N), Rdp(N);
vector<ll> max_Ldp(N), max_Rdp(N);
ll ans = 0;
FOR(i, 0, N - 1) {
cin >> P[i];
ans += P[i];
}
Ldp[0] = P[0];
max_Ldp[0] = Ldp[0];
FOR(i, 1, N - 1) {
Ldp[i] = max(P[i], Ldp[i - 1] + P[i]);
max_Ldp[i] = max(max_Ldp[i - 1], Ldp[i]);
}
Rdp[N - 1] = P[N - 1];
max_Rdp[N - 1] = Rdp[N - 1];
ROF(i, N - 2, 0) {
Rdp[i] = max(P[i], Rdp[i + 1] + P[i]);
max_Rdp[i] = max(max_Rdp[i + 1], Rdp[i]);
}
ll maxi = max(0LL, max_Ldp[N - 1]);
FOR(i, 0, N - 2) {
maxi = max(maxi, max_Ldp[i] + max_Rdp[i + 1]);
}
ans += maxi;
cout << ans;
return 0;
}

댓글남기기