cdjs의 코딩 공부방

https://acmicpc.net/problem/3307

1. 문제

- 원형의 풍선 개수 $N$이 주어진다.

- 다음 $N$개의 줄에, $x$축 위치 $x_i$와 풍선의 최대 반지름 $r_i$가 주어진다. 이 때, $x_i$는 오름차순으로 주어진다.

- 왼쪽에 있는 풍선부터 순서대로 최대 반지름 $r_i$까지 부풀리는데, 커지는 동안 다른 풍선에 접하면 부풀리기를 멈춘다.

- 왼쪽에 있는 풍선부터 차례로 풍선의 최종 반지름 값을 출력한다.

2. 힌트

힌트 1

힌트 2

힌트 3

3. 문제 관찰 과정 및 풀이

처음 생각나는 풀이는 "$i$번째 풍선에 대해, $j<i$인 모든 $j$번째 풍선을 선회하며 최소 반지름을 구한다" 이다.

당연히 위 풀이는 $O(N^2)$ 풀이이므로 시간초과가 나기 때문에, "어쩌면 아예 검사하지 않아도 되는 조건이 있을까?"를 고민해볼 수 있다.

일단 고민에 앞서, 풀이에 사용할 원의 방정식인 $(x-a)^2 + (y-b)^2 = r^2$을 사용하여 두 풍선이 맞닿는 경우의 반지름 값을 계산하는 식을 세워 보자. (어차피 최적화된 풀이로 풀어도 수식을 알아야 반지름을 구하지 않겠는가!)

두 원의 $x$좌표, $y$좌표를 각각 $(a_1, b_1), (a_2, b_2)$라고 하고, 반지름을 $r_1, r_2$라고 하자. ($a_1<a_2$)

이때, 풍선은 항상 $x$축에 맞닿으며 커지므로, $y$좌표는 항상 반지름과 동일한 $r$이 된다.

즉, 두 원의 방정식은 각각 $(x-a_1)^2 + (y-r_1)^2 = {r_1}^2$, $(x-a_2)^2 + (y-r_2)^2 = {r_2}^2$으로 나타낼 수 있다.

두 원이 맞닿아야 하므로, 피타고라스 공식을 사용하면 $(a_2 - a_1)^2 + (r_2 - r_1)^2 = (r_2 + r_1)^2$으로 나타낼 수 있고,

이를 정리하면 $(a_2 - a_1)^2 = 4r_1r_2$로 정리할 수 있다.

오른쪽의 반지름을 구할 때면 이미 그 왼쪽에 있는 반지름과 $x$축 위치는 모두 알고 있으므로, $r_2$를 찾는 수식으로 바꾸면 $r_2={(a_2-a_1)^2 \over 4r_1}$이 된다.

즉, 브루트 포스 풀이에서 사용할 풀이는 풍선 $i$와 $j<i$인 모든 $j$에 대하여, $r_i = {(a_i - a_j) \over 4r_j}$의 최소값을 찾는 것이다.

이제 다시 본론의 고민으로 돌아와서, "절대 맞닿지 않을 조건"에 대해 고민해보자.

우선 공식을 자세히 보면, $i$번째 풍선의 위치는 $a_i$는 비교해야 할 모든 ${(a_i - a_j) \over 4r_j}$에서 고정이므로, $a_j$와 $r_j$를 조금씩 변화시켜보며 $r_i$값이 어떻게 변화하는지 생각해 보자.

${(a_i - a_j) \over 4r_j}$에서 $a_j$가 조금씩 작아질수록(즉, 비교할 $j$번째 풍선의 위치가 왼쪽으로 밀릴수록), $r_i$의 값은 조금씩 커질 것이다.

또한, ${(a_i - a_j) \over 4r_j}$에서 $r_j$가 조금씩 작아질수록(즉, 비교할 $j$번째 풍선의 크기가 작아질수록), $r_i$의 값은 조금씩 커질 것이다.

즉, "$r_j$가 고정이라면 $a_j$가 작아질수록, $a_j$가 고정이라면 $r_j$가 작아질수록 $r_i$는 커진다"라는 것이다.

그러면 $r_j$와 $a_j$가 모두 다 조금씩 작아진다면? 당연히 $r_i$는 더 커진다.

그리고 이를 다시 수식으로 정리하면 $a_k<a_j<a_i$인 세 풍선 $i, j, k$에 대하여, $r_k<r_j$라면 풍선 $i$와 풍선 $j$가 맞닿기 위한 반지름의 크기보다 풍선 $i$와 풍선 $k$가 맞닿기 위한 반지름의 크기에 비해 더 크다는 것이다.

이를 토대로, "더 왼쪽에 있으면서 작은 풍선은, 그보다 오른쪽에 있으면서 더 큰 풍선이 있다면 더 이상 신경쓸 필요가 없다"라는 사실을 깨달을 수 있다!

이 사실을 토대로 문제 정답을 구현해 보자.

우선 $a_j<a_i$이고 $r_j<r_i$인 경우, 풍선 $j$는 더이상 신경쓸 필요가 없다는 사실을 알아냈으므로, 풍선 $j$는 이후의 풍선의 반지름을 계산할 때 아예 배제해야 한다.

이는 스택으로 쉽게 구현할 수 있는데, 입력은 반드시 $x$축의 오름차순으로 주어지므로 입력될때마다 스택에 넣어주면 스택의 가장 위쪽에는 현재 반지름을 구해야 할 풍선에서 가장 가까운 풍선의 정보가 담겨있을 것이다.

구현 방식은 다음과 같다.

1. 만약 이웃한 풍선과 맞닿기 위한 반지름이 이웃한 풍선의 반지름보다 크다면, 더이상 이웃한 풍선은 사용되지 못할 것이므로 스택에서 제거한 뒤, 더 왼쪽에 있는 풍선과 만날 수 있는지 확인하며 반복한다.

2. 만약 이웃한 풍선과 맞닿기 위한 반지름이 이웃한 풍선의 반지름보다 작다면, 위에서 증명한 바에 의해 이웃한 풍선보다 더 왼쪽에 있는 풍선과는 절대 맞닿을 수 없으므로 해당 반지름이 정답이 되고, 해당 풍선의 정보를 stack에 넣어준다.

이를 코드로 구현하면 다음과 같다.

4. 코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main() {
    int n;
    stack<pair<double, double>> s;
    double x[200005], r[200005];
    double min_r;   // 가장 커질 수 있는 반지름;
    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> x[i] >> r[i];
    }

    for (int i=0; i<n; i++) {
        min_r = r[i];
        while (!s.empty()) {
            double xtop = s.top().first;
            double rtop = s.top().second;
            min_r = min(min_r, (x[i] - xtop) * (x[i] - xtop) / (4*rtop));
            if (min_r >= rtop)    s.pop();
            else    break;
        }
        s.push({x[i], min_r});
        printf("%.6lf\n", min_r);
    }
}

5. 여담

부끄럽지만, 제출 20번만에 처음으로 맞았습니다!!를 받았다...

그런데 그 이유가 더 부끄러운게, 풀이는 처음부터 맞았으나 실수 출력을 이상하게 해서 계속 틀리고 있었다.

cout으로만 출력을 해버리면 너무 큰 출력은 지수 표기법으로 나와서 틀린다고 하는 것 같은데, 벌써 500솔이 넘어간 시점에서 이걸 처음 알았다는 게 진짜 레전드....

혹시라도 다른 독자들도 풀이가 맞았는데 왜 계속 틀리나 싶으면 이 점을 좀 주의하도록 하자... ;((