문제 개요
길이가 N인 두 배열 X와 H, 그리고 두 정수 D와 A가 주어집니다. 이 문제에서 은빛 여우는 N마리의 몬스터와 싸우고 있습니다. 몬스터들은 일렬로 서 있으며, i번째 몬스터의 좌표는 X[i], 체력은 H[i]입니다.
은빛 여우는 폭탄을 사용해 몬스터를 공격할 수 있습니다. 좌표 x에 폭탄을 떨어뜨리면 x − D부터 x + D까지 범위 안에 있는 모든 몬스터가 A만큼 피해를 입습니다. 모든 몬스터의 체력이 0이 되면 여우가 승리합니다. 우리는 승리하기 위해 필요한 최소 폭탄 개수를 구해야 합니다.
예시
입력이 다음과 같다고 가정해 보겠습니다.
- D = 3
- A = 2
- X = [1, 5, 9]
- H = [2, 4, 2]
이 경우 출력은 2입니다. 첫 번째 폭탄을 좌표 4에 떨어뜨리면 체력이 [0, 2, 2]가 되고, 두 번째 폭탄을 좌표 6에 떨어뜨리면 모든 체력이 [0, 0, 0]이 되기 때문입니다.
풀이 접근 방식
이 문제는 그리디(Greedy) 기법, 누적 합(Prefix Sum), 이분 탐색(Binary Search)을 조합하여 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 몬스터를 좌표순으로 정렬합니다.
- 왼쪽부터 차례대로 확인하면서, 아직 체력이 남아 있는 몬스터를 만나면 그 몬스터를 죽이는 데 필요한 최소 폭탄 수 p를 계산합니다.
- 폭탄은 항상 현재 몬스터의 위치 + D 지점에 떨어뜨리는 것이 최적입니다. 이렇게 하면 오른쪽으로 최대 2D 거리까지 떨어진 몬스터들에게 동시에 피해를 줄 수 있습니다.
- 이분 탐색으로 폭탄의 영향 범위(현재 좌표 + 2D)에 포함되는 마지막 몬스터를 찾고, 누적 합 배열 q를 이용해 해당 구간 전체에 피해량을 빠르게 갱신합니다.
구체적인 단계는 다음과 같습니다.
큰 크기의 배열 q를 선언한다
(x, h) 쌍을 담는 배열을 선언한다
n := X의 크기
d := D
a := A
i := 1부터 n까지 반복:
num[i].x := X[i - 1]
num[i].h := H[i - 1]
배열 num을 좌표 기준으로 정렬한다
sum := 0
i := 1부터 n까지 반복:
q[i] := q[i] + q[i - 1]
num[i].h := num[i].h - q[i] * a
만약 num[i].h <= 0이면:
다음 반복으로 건너뛴다
p := (num[i].h가 a로 나누어떨어지면 num[i].h / a, 아니면 num[i].h / a + 1)
tmp := num[i].x + 2 * d
sum := sum + p
q[i] := q[i] + p
l := i, r := n
l < r인 동안 반복:
mid := (l + r + 1) / 2
만약 num[mid].x <= tmp이면:
l := mid
아니면:
r := mid - 1
q[l + 1] -= p
sum을 반환한다C++ 구현 예제
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 20;
int n;
int d, a, q[maxn];
struct node{
int x, h;
bool operator<(const node& a) const{
return x < a.x;
}
} num[maxn];
int solve(int D, int A, vector<int> X, vector<int> H){
n = X.size();
d = D;
a = A;
for (int i = 1; i <= n; i++){
num[i].x = X[i - 1];
num[i].h = H[i - 1];
}
sort(num + 1, num + n + 1);
int sum = 0;
for (int i = 1; i <= n; i++){
q[i] += q[i - 1];
num[i].h -= q[i] * a;
if (num[i].h <= 0)
continue;
int p = (num[i].h % a == 0 ? num[i].h / a : num[i].h / a + 1);
int tmp = num[i].x + 2 * d;
sum += p;
q[i] += p;
int l = i, r = n;
while (l < r){
int mid = (l + r + 1) >> 1;
if (num[mid].x <= tmp)
l = mid;
else
r = mid - 1;
}
q[l + 1] -= p;
}
return sum;
}
int main(){
int D = 3;
int A = 2;
vector<int> X = { 1, 5, 9 };
vector<int> H = { 2, 4, 2 };
cout << solve(D, A, X, H) << endl;
}입력
3, 2, { 1, 5, 9 }, { 2, 4, 2 }출력
2
복잡도 분석
몬스터를 정렬하는 데 O(N log N)이 소요되며, 각 몬스터에 대해 이분 탐색이 O(log N)으로 수행됩니다. 따라서 전체 시간 복잡도는 O(N log N)입니다. 누적 합 배열 q를 활용하면 각 폭탄의 피해를 O(1)에 처리할 수 있어, 몬스터 수가 많은 경우에도 효율적으로 동작합니다.