중간에서 만난다
이번엔 가능한 모든 경우의 수를 탐색하는 브루트포스의 방법론 중에서, 중간에서 만나기 를 주제로 공부했다.
기본적인 원리는 전체 집합을 둘로 나눠 처리함으로써 그냥 모든 경우의 수를 탐색하는 것보다 더 낮은 시간복잡도 안에 계산을 끝마치는 것.
(정확한 시간복잡도 차이는 까먹었다)
사실 단일 주제라기보다 뭐 어디에 합쳐져서 문제의 난이도를 더하는 요소랄까... 그런 느낌이 있다.
이번에 풀어본 문제
일단 백준의 10712번 문제가 중간에서 만나기를 이용하는 문제.
백준 10712 財宝
오랜만에 일본어 원문 문제를 잡고 풀어봤다.
가끔은 이런 것도 해야 뭐가 늘겠지.
부족하게나마 번역을 하자면 이렇다.
문제
도적인 Anna와 Bruno는 대부호의 저택에 침입하여, 재보 1 부터 재보 N 까지의 N개의 재보를 찾아냈다.
이들 재보들을 Anna와 Bruno 둘이서 분배하게 되었다.
재보들 중 몇 개를 Anna가 가져가고, 남은 재보들 중 몇개를 Bruno가 가져간다.
같은 재보를 두 명이 가져갈 수는 없다.
Anna나 Bruno는 재보를 1개도 가져가지 않아도 된다.
또한, 남은 재보는 저택에 남겨둘 것이므로, 두 사람 모두가 가져가지 않는 재보가 있어도 된다.
각각의 재보에는 "시장가치" 와 "귀중도" 라는 2가지의 가치가 정해져 있다.
Anna가 가져가는 재보의 시장가치의 합계와 Bruno가 가져가는 재보의 시장가치의 합계의 차의 절댓값이 D 이하라면,
Anna는 공평하다고 생각하며 만족한다.
한편으로, Bruno는 Anna보다 귀중도가 높은 재보를 가지고 싶어한다.
Anna가 만족하도록 재보를 분배했을 때, Bruno가 가진 재보의 귀중도의 합계로부터 Anna가 가진 재보의 귀중도의 합계를 뺀 값의 최대치를 구하라.
입력
입력은 1 + N 줄에 걸쳐 주어진다.
1줄째에는 2개의 정수 N, D (1 ≦ N ≦ 30，0 ≦ D ≦ 10^15) 가 공백으로 구분되어 주어진다.
이것은 재보의 갯수가 N 개이며, Anna가 가진 재보의 시장가치의 합계와 Bruno가 가진 재보의 시장가치의 합계의 차의 절댓값이 D 이하라면 Anna가 만족함을 나타낸다.
다음 N개의 줄 중 i 번째 (1 ≦ i ≦ N) 줄에는 2개의 정수 Xi, Yi (0 ≦ Xi ≦ 10^15，0 ≦ Yi ≦ 10^15) 가 공백으로 구분되어 주어진다.
이것은 재보 i 의 시장가치가 Xi 이며, 귀중도가 Yi 라는것을 나타낸다.
주어지는 5개의 데이터 중 입력 1 은 N ≦ 10 을 만족한다.
또한, 입력 2 는 D = 0 을 만족한다.
출력
Anna가 만족하도록 재보를 분배했을 때, Bruno가 가진 재보의 귀중도의 합계에서 Anna가 가진 재보의 귀중도의 합계를 뺀 값의 최대치를 첫째 줄에 출력한다.
중간에서 만나기는 역시 뭔갈 더 끼운다
아예 골드 이하의 비교적 낮은 난이도의 문제라면 모르겠지만, 이 쯤 되면 중간에서 만나기는 덤일 뿐, 뭔가 더 붙어서 문제가 된다.
이 문제만 해도 중간에서 만나기라는 기본 개념을 쓰는 건 맞지만, 여기서는 해설에 잠깐 언급된 덱을 이용하라는 말, 즉 단조 큐를 사용하는 것을 따르지 않으면 시간이 모자라게 되어있는 듯 하다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
ll N, D, ans;
vector<pll> v, arr[2];
deque<pll> dq;
void dfs(int idx, int s, int e, ll x, ll y) {//각 재보에 대해 Anna가 가져가는지 Bruno가 가져가는지 아무도 안 가져가는지 경우의 수를 만듦
if (s == e) {
arr[idx].push_back({ x,y });
return;
}
dfs(idx, s + 1, e, x + v[s].first, y + v[s].second);
dfs(idx, s + 1, e, x - v[s].first, y - v[s].second);
dfs(idx, s + 1, e, x, y);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> N >> D;
v.resize(N);
for (pll& i : v) cin >> i.first >> i.second;
dfs(0, 0, N / 2, 0, 0);
dfs(1, N / 2, N, 0, 0);
//2개의 집단의 경우의 수를 만듦
sort(arr[0].begin(), arr[0].end());
sort(arr[1].begin(), arr[1].end());
//정렬
ll j = 0;
for (pll i : arr[0]) {
for (; j < arr[1].size() && arr[1][j].first <= i.first + D; j++) {
while (dq.size() && dq.back().second >= arr[1][j].second) dq.pop_back();
dq.push_back(arr[1][j]);
}
while (dq.size() && dq.front().first < i.first - D) dq.pop_front();
ll tmp = dq.size() ? i.second - dq.front().second : -1;
if (ans < tmp) ans = tmp;
//단조 큐를 이용해 보면서 최댓값을 취함
}
cout << ans;
}여담
위에도 언급된 바 있지만, 단순히 중간에서 만나기 외에도 단조 큐를 이용해야 풀리는데, 이걸 꽤나 늦게 알아서 많은 시도를 해야 했다.
역시 PS의 세계는 무서워...
