[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. 문제Permalink
25049. 뮤직 플레이리스트 (2022 DGIST 현풍전산배 알고리즘 대회 F번)
백준 25049번 - 뮤직 플레이리스트 (https://www.acmicpc.net/problem/25049)
2. 풀이Permalink
- 최대 두 번 현재 듣고 있는 곡보다 플레이리스트 상에서 앞에 위치했던 곡으로 돌아가 그 곡부터 다시 듣는다.
- 같은 노래를 세 번 이상 듣게 되는 경우는 없도록 한다.
위 두 사실을 조합하면, 전체 합에 어떤 i∼j(1≤i,j≤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∼t)과 오른쪽(t+1∼N) 구간을 나누고, 각각의 구간에서 부분합의 최댓값을 찾는 방법을 생각해볼 수 있다.
기준점을 기준으로 왼쪽 구간(1∼t)은 → 방향으로 dp를 계산하고, 오른쪽 구간(t+1∼N)은 ← 방향으로 dp를 계산한다. 그리고 각 구간에서의 dp[i]
의 최댓값을 더하면, 해당 기준점에서의 부분합 총합의 최댓값을 구할 수 있다. 이를 모든 기준점에 대해서 수행해야 정답을 구할 수 있다.
연산 과정을 줄이기 위해, → 방향으로 전체 idx에 대해 dp값을 전부 구하고(Ldp), ← 방향으로 전체 idx에 대해 dp값을 전부 구한다(Rdp). 그리고 Ldp의 구간별 최댓값, Rdp의 구간별 최댓값도 새로운 배열에 각각 계산하여 담는다. 이렇게 미리 처리해놓으면, 기준점을 설정했을 때 O(N)으로 최댓값을 갱신할 수 있다.
t=0인 경우와 t=N인 경우는 전체에 대해서 최대 부분합 구간을 하나만 찾는 과정이라고 간주할 수 있으므로, 따로 부분합 구간이 하나인 경우를 구할 필요는 없다.
이렇게 구한 부분합의 총합이 0보다 작을 경우는 부분합을 더하면 안 된다. 이는 되돌아가는 작업을 한 번도 하지 않는다는 것을 의미한다.
3. 채점 결과Permalink
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; | |
} |
댓글남기기