문제 요약
땅 속에는 포화이진트리의 형태로 기름 탱크가 있다. 단말 노드들에는 펌프가 설치되어 있어 단말 노드에서부터 시작해 땅 속에서 펌프를 이용하여 석유를 끌어올리는데, 각 기름 탱크를 가득 채우기 위한 최소 시간을 구하여라. 단, 양 쪽 자식 노드의 탱크가 가득 채워져 있지 않다면 기름은 비어있는 탱크 쪽으로 흐르게 된다.
풀이
트리 순회를 이용하여 문제를 풀 수도 있겠지만, 이는 시간이 너무 오래 걸리기 때문에 더 효율적인 방법을 생각해야 한다.
친절하게 문제에서 주어지는 포화이진트리의 특성을 이용한다면, 반복문을 통해 간단하게 (1) 각 노드가 1초에 전달할 수 있는 기름의 양, (2) 각 노드를 가득 채우기 위해 필요한 기름의 양 이 두가지를 구할 수 있다.
추가적으로 (2)를 구하기 위해 염두해야 할 문제의 규칙은 어떤 노드에 기름을 채우기 위해서는 해당 노드의 subtree에 속하는 모든 노드에 기름이 가득 차야 한다는 것이다.
- 가득 차 있지 않다면, 빈 노드 방향으로 기름이 흐를 것이기 때문에.
다시 말해, (2)는 해당 노드에 채울 수 있는 용량 뿐만 아니라 subtree들의 용량만큼 더 필요하다는 것이다.
위 두 가지를 전처리를 통해 미리 구했다면, 한 가지 더 고려해야 하는 부분은 어떤 노드에 기름이 차는 방식은 흘러 내려오는 것과 펌프를 통해 올라오는 것인데 펌프를 통해 올라오는 양은 (2)를 통해 미리 구했기 때문에 (3) 흘러 내려오는 양을 더 고려해야 한다.
(3)을 고려하기 위해서는 위에서부터 흐르는 기름을 어떤 노드에 담기 위해 가득 차 있어야 하는 노드의 번호를 기록하면 된다. 이 노드는 포화이진트리 그림을 그려놓고 보면 쉽게 알 수 있다.
위 그림을 예시로 들면, 13번 노드에 흐르는 기름을 담기 위해서는 12번, 7번, 2번 노드는 가득 차 있어야 한다.
여기까지 접근했다면, 어떤 시간을 정해놓고 그 시간에 해당 노드의 용량을 가득 채울 수 있을지 없을지 구할 수 있기 때문에 시간에 대해 Parametric Search를 진행하면 O(NlogT)만에 답을 구할 수 있다.
코드
#include<cstdio>
#include<climits>
#include<vector>
#include<algorithm>
using namespace std;
int N;
long long W[262144], SW[262144], o[262144], ans[262144];
bool go(int i, long long t, vector<int> &p) {
long long sum = o[i] * t;
for (auto a : p) sum += max(0ll, t * o[a] - SW[a]);
return sum >= SW[i];
}
int main() {
scanf("%d", &N);
for (int i = 1; i <= N; i++) scanf("%lld", &W[i]);
for (int i = N; i; i--) {
if (2 * i > N) {
SW[i] = W[i];
o[i] = 1;
}
else {
SW[i] = W[i] + SW[2 * i] + SW[2 * i + 1];
o[i] = o[2 * i] * 2;
}
}
for (int i = 1; i <= N; i++) {
long long l = 0, r = INT_MAX;
vector<int> p;
for (int j = i; j > 1; j /= 2) p.push_back(j + (j % 2 ? -1 : 1));
while (l <= r) {
long long m = (l + r) / 2;
go(i, m, p) ? r = m - 1 : l = m + 1;
}
ans[i] = l;
}
for (int i = 1; i <= N; i++) printf("%lld ", ans[i]);
return 0;
}