BOJ 11982 - Angry cow (그리디, 전처리dp, 투포인터)

https://www.acmicpc.net/problem/11982

어렵다

공식홈페이지와 rdd6584님의 코드를 보며 공부했습니다.

 

<문제설명>

일직선위에 최대 5e4개의 표적이 n개 주어진다. 폭발반경이 R인 폭탄을 일직선 위에 던지려고 한다.

 

표적은 터지면 이전 폭발반경보다 1 작은 만큼의 폭발반경을 가지며 연쇄폭발한다.

 

적절한 곳에 폭탄을 던진다면 모든 표적을 부수기 위해 필요한 폭탄의 최소 폭발반경은 몇일까? 소수점 첫 자리까지 나타내라

 

 

<풀이>

폭탄은 어떤 두 표적 정 가운데에 떨어지는 것이 최적이다. ->(x+y)/2로 표적의 위치를 특정할 것이므로 표적의 위치는 xxx.5 혹은 xxx.0이다. 모든 표적의 좌표를 두배로 하고 폭발반경이 2씩 줄어든다고 처리하면 정수연산만으로 풀 수 있다.

표적은 오름차순 정렬해둔다.

 

l[i] : i 이후 어딘가 폭탄을 투하해서 i번 표적이 터졌을 때, 0~i번 표적을 모두 터뜨리기 위한 i번 표적의 최소 폭발 반경

r[i] : i 이전 어딘가 폭탄을 투하해서 i번 표적이 터졌을 때, i~n-1번 표적을 모두 터뜨리기 위한 i번 표적의 최소 폭발 반경

 

폭탄이 lo, hi번 표적 정 가운데에 떨어져 lo~hi번 표적을 모두 터뜨렸을 때, 0~n-1번 표적을 모두 터뜨리기 위한 최소 폭발 반경을 lo,hi를 조정해가며 갱신해주면 답을 구할 수 있다.

 

정확히 lo,hi를 터뜨릴 정도만 하면 되는지, lo이전 표적을 터뜨리기 위해 좀 더 넓은 반경이 필요한지, hi이후 표적을 터뜨리기 위해 좀 더 넓은 반경이 필요한지 비교해주면 된다.

ll temp = max({a[hi]-a[lo]/2, l[lo]+2, r[hi]+2})
rst = min(rst,temp)

a[hi]-a[lo]/2는 폭탄의 폭발반경이고, l,r은 그 표적의 연쇄 폭발반경이므로 비교할 때 2를 더한 값으로 비교해야 한다.

 

---

 

투포인터 lo, hi는 어떻게 조절하면 될까? 

가장 단순하게 모든 표적을 조지려면 0번째, n-1번째 표적의 정 가운데에 떨어뜨리면 된다. 

 

temp = max({x,y,z}) 에서 lo,hi의 이동에 따라 x는 단조감소, y,z는 단조증가한다.

temp의 형태는 아래볼록 이차함수 꼴이다.

가능한 temp값중 가장 작은 값을 구하고자 한다.

y,z의 증가폭을 최대한 작게 해야 원하는 값을 얻을 수 있다. (??)

int lo = 0, hi = n - 1;
ll rst = INF;
while (lo < hi) {
	ll temp = max({ (a[hi] - a[lo]) / 2, l[lo] + 2, r[hi] + 2 });
	if (rst < temp) break; //이 이후로 temp는 계속 커질 것
	rst = temp;
	if (l[lo + 1] < r[hi - 1]) lo++;
	else hi--;
}

 

---

 

l은 어떻게 초기화 할까? (r은 l 초기화하는 것에 반대로 해주면 된다.)

l[i] : 어딘가 폭탄을 투하해서 i번 표적이 터졌을 때, 0~i번 표적을 모두 터뜨리기 위한 i번 표적의 최소 폭발 반경

0<=p<i를 만족하는 p에 대해 p번째 표적이 i번 표적의 다음 연쇄폭발을 일으키는 경우

 

i번 표적은 최소 a[i]-a[p]만큼의 폭발반경을 가져야 하고(i~p까지 폭발이 닿아야 함.)

그리고 최소l[p]+2 만큼의 폭발반경을 가져야 한다.(p에서 연쇄폭발로 모든 표적이 다 터져야 함)

for (int i = 1; i < n; i++) {
	for (int p = 0; p < i; p++) {
		ll temp = max(a[i] - a[p], l[p] + 2);
		l[i] = min(l[i], temp);
	}
}

 

이 O(n^2) 코드를 조금만 최적화 해보자.

l[i]를 구할 때 i에 의해 prev표적이 처음으로 연쇄폭발을 일으키는 것이 최적이었다면, 

l[i+1]를 구할 때, i+1에 의해 prev표적 이후의 표적이 처음으로 연쇄폭발을 일으키는 것이 최적이다.

int prev=0;
for (int i = 1; i < n; i++) {
	for (int p = prev; p < i; p++) {
		ll temp = max(a[i] - a[p], l[p] + 2);
		if (l[i] > temp) {
			l[i] = temp;
			prev = p;
		}
	}
}

 

평균적으로 외부 for문에서 내부 for문의 수행시간 합이 O(n)이다. 이걸로도 통과는 되지만 충분하지 않다.

최악의 경우 모든 i에 대해 같은 표적을 처음으로 연쇄폭발시키는 것이 최적인 경우 tle가 날 수 있을 것으로 보임.

 

좀더 최적화해보자.

temp = max(a[i]-a[p], l[p]+2)에서 p가 증가함에 따라 a[i]-a[p]는 단조감소고, l[p]+2는 단조증가한다.  

temp는 아래볼록 이차함수 꼴이거나 단조증가한다.

ex) 2 20 22 24 26인 경우를 손으로 써보자.

 

감소하는 곳까지 갱신하고, 증가하거나 정체하는 구간을 마주하면 바로 탈출해주면 된다. O(n)

for (int i = 1; i < n; i++) {
	for (int p = prev; p < i; p++) {
		int temp = max(a[i] - a[p], l[p] + 2);
		if (l[i] > temp) {
			l[i] = temp;
			prev = p;
		}
		else break;
	}
}

 

 

 

 

 

<코드>

const int MAX = 1e5 + 4;
const int INF = 1e9;

int a[MAX], l[MAX], r[MAX], n;

int main() {
	FAST; cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		a[i] *= 2;
	}
	sort(a, a + n);

	fill(l, l + n, INF);
	fill(r, r + n, INF);
	l[0] = r[n - 1] = -2;
	int prev = 0;
	for (int i = 1; i < n; i++) {
		for (int p = prev; p < i; p++) {
			int temp = max(a[i] - a[p], l[p] + 2);
			if (l[i] > temp) {
				l[i] = temp;
				prev = p;
			}
			else break;
		}
	}

	prev = n - 1;
	for (int i = n - 2; i >= 0; i--) {
		for (int p = prev; p > i; p--) {
			int temp = max(a[p] - a[i], r[p] + 2);
			if (r[i] > temp) {
				r[i] = temp;
				prev = p;
			}
			else break;
		}
	}
	
	int lo = 0, hi = n - 1;
	int rst = INF;
	while (lo < hi) {
		int temp = max({ (a[hi] - a[lo]) / 2, l[lo] + 2, r[hi] + 2 });
		if (rst < temp) break;
		rst = temp;
		if (l[lo + 1] < r[hi - 1]) lo++;
		else hi--;
	}

	cout << rst / 2 << "." << (rst % 2 ? 5 : 0) << '\n';	
}

 

<생각>

1. 좌표 두배해서 정수연산만 사용하도록.

2. 폭탄은 항상 어떤 두 표적 정 중앙에 떨어트리는 것이 최적임

3. lo~hi 사이에 폭탄을 떨어트릴 때 필요한 최소 폭발반경을 temp라고 할 때, 

temp = max{x,y,z}

x는 단조감소, y,z는 단조증가한다는 점에서 temp의 모양이 아래볼록 이차함수꼴이라는 것 확인.

lo,hi를 움직이다보면 최종적으론 x보다 max(y,z)가 클 수밖에없음. 결국 max(y,z)가 temp를 결정하게 되므로

-> 한번 lo,hi를 움직일때마다 최대한 y,z가 적게 움직이도록 해야함.

 

4. l,r 배열을 만들 때, 위 풀이의 O(n^2) 점화식에 사용된 아이디어 확인.

그 후 최적화.

 

 

3번과정에서 쓴 논리는 뭔지 궁금하다. 그냥 그리디인건가?