[백준 2515번] 전시장 (C++)
https://www.acmicpc.net/problem/2515
문제는 직관적으로 이해하기 어렵지 않았지만 어떻게 풀어야할지 감이 잘 안오는 문제다.
하지만 N = 30만이므로 완전탐색은 불가능하고 모든 그림을 배치하고 살펴보는 DFS, BFS 방식도 불가능하다고 판단했다.
Greedy 탐욕법
탐욕법은 어떨까? 그림의 가격순으로 정렬하고 가격이 높은 것부터 배치하고 다음 그림을 배치할 수 있다면 배치하는 방식을 사용하면 어떨까.
그리디를 사용하기 위해서는 두가지 조건을 만족해야한다.
1. 탐욕 선택 조건: 앞에서 탐욕 선택한 값이 이후의 값에 영향을 주어선 안된다.
2. 최적 부분 조건: 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해이다.
이 문제에서 탐욕 선택 조건에서 문제가 있다. 만약 100의 그림을 선택했다면 이 선택은 이후에 영향을 미쳐선 안된다. 하지만 이 그림 100을 선택함으로 인해 뒤의 모든 그림을 선택할 수 없고, 모든 그림을 선택했을 때는 200의 이득을 얻을 수 있었다면 탐욕 선택 조건에 위배된다.
두번째 최적부분 조건은 큰 문제를 작게 쪼개도 성립해야하는데 첫번째 조건부터 성립하지 않으니 두번째도 성립하지 않는다. 쪼갠 작은 문제에서도 1번이 위배되기 때문에
DP 동적계획법
DP가 성립하려면 같은 문제가 반복적으로 나오고 그것을 메모이제이션을 통해 최적화할 수 있어야한다.
이 문제를 DP 라 가정하고 그림을 높이 순으로 정렬 후 i 번째 그림까지 확인했을 때 가장 큰 최적값이라고 하자.
즉,
dp[i] = i번째 까지 가장 큰 값
그리고 dp[0] = 가장 첫 그림의 value가 될 것이다.
6 4
15 80
8 230
10 100
17 200
20 75
26 80
주어진 예제를 사용해보면
8 230
10 100
15 80
17 200
20 75
26 80
첫번째 dp값은 무조건 선택해야하므로
dp[0] = 230
두번째부터는 자기 이전의 그림들을 살펴봐야한다.
0번째 그림은 높이가 4이상 차이나지 않으므로 선택할 수 없다.
그러므로 0번째 혹은 1번째 하나만 선택해야한다. 값이 더 큰 230을 선택한다. dp[1] = 230
세번째도 마찬가지다.
0번째: 선택가능
1번째: 선택가능
dp[2] = dp[1] + value[2]
N까지 반복,
이것을 코드로 표현하면
for(int i = 1; i < N; i++){
for(int j = 0; j < i; j++){
if(높이 차이가 S보다 크면){
dp[i] = max(dp[i - 1], dp[j] + i의 가격)
}else{
dp[i] = max(dp[i - 1], i의 가격)
}
}
}
모든 값을 확인해야하는 완전탐색인 O(N!)에서 , 최적의 해만을 저장하고 필요시에만 가져오는 메모이제이션 방식으로 최적화하여 O(N^2) 으로 줄였다. DP가 가능한 것으로 확인되었다. 최적 부분 조건을 만족하면서 중복된 연산을 저장해서 사용하였다.
하지만 N이 30만이기 때문에 아직부족하다.
이분탐색
두번째 for문을 도는 이유는 i 번 그림과 0~ (i - 1) 번 그림을 비교하여 함께 배치할 수 있는 높이 차이가 S인 값 중 최댓값을 찾기 위해서이다.
즉, 1 2 3 4 에서 8과 5이상 차이나는 것들 중 가장 큰 값을 찾기 위해 1부터4 를 모두 비교하고있다!
우리는 DP를 통해 우측으로 갈 수록 최댓값을 갱신해두고 있다. 그러므로 S이상 차이나는 것들 중 upper바운드를 통해 가장 우측값을 찾고 그것과 연산을 해주면 된다. 이분탐색의 시간복잡도는 log(N)을 자랑하므로 NlogN 으로 문제를 해결할 수 있다.
DP라는 것을 알아채는 것도 쉬운것이 아니었고 이중for 문 점화식을 찾아내는 것도 쉽지 않았으며 그것을 이분탐색으로 최적화한다고 눈치채는 것은 더더욱 어려운 문제였다..
이런것을 풀어낼 수 있어야 진짜 실력자라고 할 수 있을 것이다.
int bin_search(int n){
int lo = -1;
int hi = n;
int mid = (lo + hi) / 2;
while(lo + 1 < hi){
mid = (hi + lo) / 2; // mid 는 인덱스임
if(grims[n].first - grims[mid].first >= S){
lo = mid;
}else{
hi = mid;
}
}
return lo;
}
* lo + 1 < hi 조건은 mid 값이 언제나 lo~ hi 사이에 있음을 보장한다. 지금여기선 0~n-1 을 확인해야하므로 lo, hi를 저렇게 잡아두었다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<pair<int, int>> grims;
int dp[300001];
int S, N;
int bin_search(int n){
int lo = -1;
int hi = n;
int mid = (lo + hi) / 2;
while(lo + 1 < hi){
mid = (hi + lo) / 2; // mid 는 인덱스임
if(grims[n].first - grims[mid].first >= S){
lo = mid;
}else{
hi = mid;
}
}
return lo;
}
int main(){
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
cin >> N >> S;
for(int i = 0; i < N; i++){
int x, y;
cin >> x >> y;
grims.push_back({x, y});
}
sort(grims.begin(), grims.end());
dp[0] = grims[0].second;
for(int i = 1; i < N; i++){
int idx = bin_search(i);
if(idx == -1)
dp[i] = max(dp[i - 1], grims[i].second);
else
dp[i] = max(dp[i - 1], dp[idx] + grims[i].second);
}
cout << dp[N - 1] << '\n';
}
