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솔이 넘어간 시점에서 이걸 처음 알았다는 게 진짜 레전드....

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

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

1. 문제

- 첫 줄에 메뉴의 종류 $N$이 주어짐.

- 두 번째 줄에 각 메뉴의 스코빌 지수가 주어짐.

- 가능한 모든 2 가지 이상의 메뉴 조합들에서, (가장 높은 스코빌 지수) - (가장 낮은 스코빌 지수)의 합을 구하여라.

2. 힌트

힌트 1

힌트 2

힌트 3

3. 문제 관찰 과정 및 풀이

가장 처음 할 수 있는 생각은 "모든 조합을 구한 뒤에 (최대, 최소) 쌍을 구해서 더하자" 이다.

물론 이렇게 풀면 시간 초과가 나겠지만, 사실 저 아이디어는 굉장히 중요한 아이디어를 내포하고 있다.

"어차피 어떤 조합을 선택하든, 최대값과 최소값만 알면 된다" 라는 것이다.

이 아이디어를 조금만 더 확장해 보자.

많은 문제에서 사용되는, "순서 바꾸기" 테크닉을 사용할 차례이다.

즉, 조합을 선택한 뒤에 최대, 최소값을 구하는 것이 아니라, 먼저 최대, 최소값을 선택한 뒤에 조합들의 개수를 세는 것이다.

(어차피 조합이 어떻든지 최대값과 최소값만 알면 되기 때문에 이런 접근이 가능하다.)

가령, 문제의 예제 2인,

6
1 4 5 5 6 10

를 생각해 보자.

일단 최대값 먼저 생각하면,

10을 최대값으로 갖는 조합은 총 $2^5-1$가지이므로, 그 모든 $2^5-1$가지의 조합에서는 10을 고통 지수에 더해야 한다.

6을 최대값으로 갖는 조합은 총 $2^4-1$가지이므로, 그 모든 $2^4-1$가지의 조합에서는 6을 고통 지수에 더해야 한다.

...

1을 최대값으로 갖는 조합은 총 $2^0-1 = 0$가지이므로, 1은 어떤 조합에서도 고통 지수에 더해지지 않는다.

다음으로 최소값을 생각하면,

1을 최소값으로 갖는 조합은 총 $2^5-1$가지이므로, 그 모든 $2^5-1$가지의 조합에서는 1을 고통 지수에 빼야 한다.

4를 최소값으로 갖는 조합은 총 $2^4-1$가지이므로, 그 모든 $2^4-1$가지의 조합에서는 4를 고통 지수에 빼야 한다.

...

10을 최소값으로 갖는 조합은 총 $2^0-1 = 0$가지이므로, 10은 어떤 조합에서도 고통 지수에 빼지지 않는다.

이를 일반화 하면, 모든 스코빌지수를 정렬한 값이 $A[1], A[2], \cdots , A[n]$ 이라고 하면, 정답은

$$(2^{N-1}-1)(A[n]-A[1]) + (2^{N-2}-1)(A[n-1]-A[2]) + \cdots + (2^0-1)(A[1]-A[n])$$

으로 계산할 수 있다.

구현에서도 몇 가지 포인트가 있는데, $2^x-1$을 $N$번 그냥 계산하게 되면 시간초과가 나므로 $2^x-1$을 미리 저장하는 배열을 하나 만들어 둬야 한다.

또한, C++에서의 음수의 나머지 연산에 유의하며 연산을 진행해야 한다.

4. 코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main() {
    ll n;
    ll arr[300005];
    ll two[300005];
    ll MOD = 1'000'000'007;
    ll temp = 1;
    ll p=0, m=0;

    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> arr[i];
    }

    for (int i=0; i<n; i++) {
        two[i] = temp-1;
        temp*=2;
        temp%=MOD;
    }

    sort(arr, arr+n);

    for (int i=n-1; i>0; i--) {
        p += two[i] * arr[i];
        m += two[i] * arr[n-1-i];
        p%=MOD;
        m%=MOD;
    }
    cout << (p%MOD + MOD - m%MOD) % MOD << '\n';
}

5. 여담

사실 나머지 연산 잘못해서 무려 10번가량이나 박아버렸다.

나머지 연산 귀찮다고 안보다가 결국에는 피를 보는 일이 생겼다... 대회에서 안이런걸 다행으로 여겨야겠다.

위 방식은 $2^x-1$을 메모이제이션 하는 방식을 사용했지만, 분할 정복을 활용하여 제곱을 계산해도 시간 안에 풀 수 있다.

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

1. 문제

- x축 위에 점들이 N개($n \leq 100,000$) 있음

- 초기에 i번째 점에서 시작해서, 모든 N개의 점을 순회할 수 있는지 확인해야 함

- 단, 이동 시에는 이전에 이동했던 거리의 최소 2배 이상 이동해야 함

- 각 N개의 점에 대해서, 각 점에서 출발하여 모든 N개의 점을 순회할 수 있으면 YES를, 없으면 NO를 출력함.

1-1. 힌트

힌트 1

힌트 2

힌트 3

2. 문제 관찰 과정

우선, 문제의 조건과 시간 제한을 살펴보자.

모든 테스트케이스에서의 N의 범위가 $N \leq 1,000,000$이므로, 각 $N$개의 점에 대해서 200번 이하의 연산을 진행해야 시간 초과가 나지 않는다(대략 1억회의 연산을 1초라 가정함). 하지만 정답을 YES로 출력하는 점에 대해서는 필연적으로 해당 점에서부터 모든 $N$개의 점을 순회해야 하므로 시간복잡도가 $O(N^2)$이 된다. 즉, 문제에 숨겨진 또 다른 조건을 찾아야 한다는 뜻이다.

문제에서 이동 거리는 최소 1이고, 다음에 이동할 때는 이전 거리의 2배는 이동해야 한다고 제시하였다. 그런데, $2^{21}=2,097,152$이기 때문에 초기에 아무리 조금 움직였더라도 추가로 20번만 이동하더라도 이미 x축의 범위인 $10^{-6} \leq a_i \leq 10^6$에 의해 더 이상 다음 점으로의 이동이 불가능하다. 즉, 어차피 각 테스트케이스에서 이동 횟수가 20보다 크다면 정답은 무조건 NO가 된다. 이 경우, 움직인 횟수를 $M$이라 하면 시간복잡도가 테스트케이스 당 $O(M^2)$이 되어도 $T{M}^2 = 22,050,000$이므로 시간 안에 풀이가 가능하다.

그러나 $N$개의 점에 대하여, $i$번째 이동에 $N-i$개의 점으로 이동이 가능하므로 완전 탐색 시뮬레이션을 돌리게 되면 시간 복잡도가 $N!$이 되어 시간 안에 풀이가 불가능하다. 어떻게 $O(N!)$의 시간복잡도를 $O(N^2)$으로 바꿀 수 있을까?

3. 풀이

위 문제 풀이의 가장 중요한 아이디어는 다른 점을 건너뛰고 이동하면 안 된다는 것이다.

예를 들어, $A < B < C $인 세 점에서 $A$에서 $C$로 이동한 경우를 생각해 보자.

점 $A$와 점$C$ 사이의 거리가 $x$라고 두면, 다음으로 이동할 수 있는 거리는 최소 $2x$이다.

이 때, 점 $C$에서 오른쪽으로 $y (2x \leq y)$만큼 이동하면 그 다음으로 이동할 수 있는 위치는 $C+2y$ 이상, $C-2y$이하이므로 결코 점 $B$에 도달할 수 없다.

마찬가지로 점$C$에서 왼쪽으로 $y$만큼 이동하는 경우에서도 결코 점 $B$로 도달할 수 없다.

이렇듯, 다른 점을 건너뛰고 이동하면 필연적으로 그 사이에 있는 점으로는 도달할 수 없다는 점을 확인할 수 있다.

하지만 이 사실을 알아내더라도 좌/우로 모두 이동하는 것을 완전 탐색으로 시뮬레이션을 돌리게 되면 시간복잡도는 여전히 $O(2^N)$으로, 제한 시간 내에 풀이가 불가능하다.

좌/우 중 어느 것을 고르는 것이 최적일지 판단은 어떻게 할 수 있을까?

문제를 간단히 하기 위해, $A < B < C$ 인 세 점 중 점 $B$ 에서 시작하는 경우를 예시로 들어 보자.

$A$와 $B$ 사이의 거리를 $x$, $B$와 $C$ 사이의 거리를 $y$라고 하자.

점$B$에서 점$A$로 이동하는 경우 다음으로 이동할 수 있는 위치는 $A+2x$ 이상 $A-2x$ 이하이다.

이 때, $y<x$인 경우 $A-2x < C < A+2x$이므로 절대로 점$C$로 이동할 수 없다.

즉, 좌/우 중 한 곳을 선택하는 경우, 무조건 짧은 거리만을 선택해야 한다는 것이다.

위 아이디어들을 종합하면, 다음과 같은 풀이가 도출된다.

"$N$개의 점에 대해, 항상 좌/우 중에서 가장 가까운 거리에 있는 점으로 이동한다(이 때, 좌/우의 거리가 동일한 경우에는 좌/우 모두 이동해 본다). 그렇게 이동하면서 다음에 이동할 점이 결코 도달 불가능한 점에 있을 경우 답은 NO이고, 끝까지 $N$번째 점으로 이동했다면 답은 YES이다."

이것을 코드로 그대로 구현해 보자.

4. 코드

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

int n;
vector<ll> a;

bool solve(int x, int r, int l, ll gap) {
    if (l>=0 && r<n) {
        if (a[r]-a[x]<a[x]-a[l]) {
            if (gap>a[r]-a[x])    return false;
            return solve(r, r+1, l, (a[r]-a[x])*2);
        }
        else if (a[r]-a[x]>a[x]-a[l]){
            if (gap>a[x]-a[l])    return false;
            return solve(l, r, l-1, (a[x]-a[l])*2);
        }
        else {
            return (solve(l, r, l-1, (a[x]-a[l])*2) || solve(r, r+1, l, (a[r]-a[x])*2));
        }
    }
    else if (l>=0) {
        if (gap>a[x]-a[l])    return false;
        return solve(l, r, l-1, (a[x]-a[l])*2);
    }
    else if (r<n) {
        if (gap>a[r]-a[x])    return false;
        return solve(r, r+1, l, (a[r]-a[x])*2);
    }
    else {
        return true;
    }
}

int main()
{
    int t;
    int r, l;
    ll gap;
    
    cin >> t;
    while (t--) {
        int x=0;
        scanf("%d",&n);
        a = vector<ll>(n, 0);
        
        for (int i=0; i<n; i++) {
            scanf("%lld",&a[i]);
        }
        
        for (int i=0; i<n; i++) {
            gap=1234567890;
            r=i+1;
            l=i-1;

            if (l>=0)    gap = min(gap, a[i]-a[l]);
            if (r<n)    gap = min(gap, a[r]-a[i]);
            
            if (solve(i, r, l, gap))    printf("YES\n");
            else    printf("NO\n");
        }
    }
}

5. 여담

위 풀이에서 최악의 케이스는 좌우가 동일한게 계속 반복되서 나오는 경우인데, 제한 조건 안에서 아무리 좌우가 동일하게 반복되어봤자 그렇게까지 많은 케이스를 방문하지 않게 되므로, 시간 내에 충분히 풀이가 가능하다.

난이도 기여를 보니까 의도된 풀이는 DP인 것 같은데, 나중에 그 풀이도 살펴봐야겠다.

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

1. 문제

- 컴퓨터의 개수 $N$, 케이블선의 개수 $P$, 공짜로 제공하는 케이블선의 개수 $K$가 주어진다.

- 다음 $P$개의 줄에, 연결된 컴퓨터 쌍 A, B와 연결 비용 C가 주어진다.

- 초기에는 1번 컴퓨터에만 인터넷이 연결되어 있고, $N$번 컴퓨터에 인터넷을 연결하는 것이 목표이다. (1, $N$을 제외한 다른 컴퓨터는 인터넷에 연결되지 않아도 된다.)

- 연결하는 비용은 연결한 케이블선을 나열했을 때, $K+1$번째로 비용이 높은 케이블선의 비용이다.

2. 힌트

힌트 1

힌트 2

힌트 3

3. 문제 관찰 과정 및 풀이

우선, 가장 간단한 $K=0$인 경우부터 생각해 보자.

$K=0$인 경우, 무료로 주는 케이블선이 없으므로 모든 케이블선을 직접 연결해야 한다.

이 경우에는 케이블선을 최적으로 고르는 방법은 비용이 가장 낮은 케이블선부터 하나씩 차례로 연결해 보면서, $1$번 컴퓨터와 $N$번 컴퓨터가 연결될때 까지, 그리디하게 계속 연결해 보는 것이다.

그러나, $K>0$인 경우를 생각해 보자.

가장 간단하게 생각할 수 있는 방법은 $P$개의 간선 중 $K$개를 모두 고른 다음에, 위에서 말했던 해결 방법을 그대로 적용하는 것이다.

실제로 $K=1$인 경우에는 이런 방법이 통할 수 있겠지만, $K < N \leq 1,000$이고, $P \leq 10,000$이므로 $K, P$가 커지면 이 방법은 시간초과가 나게 될 것이다.

$P$개의 케이블선 중 무료로 받을 $K$개를 모두 탐색하며 문제를 푸는 것은 어떻게 해도 불가능하다는 사실을 알았으니, 여기서 몇 가지 고민들을 할 수 있다.

우선, $P$개의 케이블선 중 $K$개를 고르는 것을 그리디하게 구할 수 있는지 고민해 보면, 어떻게 해도 불가능하다는 것을 깨달을 수 있다.

가장 비싼 $K$개의 케이블선을 고르는 경우는 당연히 최선이 아닐 뿐더러, $K$개의 케이블선을 골랐을 때와 고르지 않았을 때 최소 비용의 경로가 아예 달라지기 때문이다. 즉, 무료로 받은 $K$개를 제외한 간선을 연결하기 전에는 $K$개의 무료 간선을 고를 수 없다는 것이다.

여기서 잠깐 종합해 보자.

$K=0$이라고 생각했을 때는 그리디하게 케이블선들을 연결할 수 있었다.

그렇다면 $K>0$인 경우는 어떨까?

이미 그리디하게 연결된 케이블선들 중 가장 높은 비용의 케이블선 $K$개를 무료로 받을 때, 무료로 받은 케이블선 비용 미만의 케이블선과, 지금 무료로 받은 케이블선들만으로 $1$번 컴퓨터와 $N$번 컴퓨터를 연결할 수 있다면 최소 비용은 조금씩 낮아지게 된다.

이 때, 만약 처음에 $X$ 이하의 비용만으로 이미 $1$번 컴퓨터와 $N$번 컴퓨터를 연결할 수 있었다고 한다면, 무료로 받는 케이블선이 아닌 이상 $X+1$ 이상의 비용을 가진 케이블선을 추가로 고를 필요가 전혀 없다.

또한, 비용이 $X$ 이하인 케이블선만 고른다면 고른 케이블선이 $1$번 컴퓨터와 $N$번 컴퓨터를 연결하는지 여부와 관계 없이 어차피 총 비용은 $X$ 이하이다.

따라서, 우리는 이런 풀이를 생각해볼 수 있다.

"비용이 $X$ 이하인 케이블선들을 모두 고른 뒤에, $K$개 이하의 케이블선만으로 $1$번 컴퓨터와 $N$번 컴퓨터까지 연결할 수 있다면, 총 비용은 $X$ 이하일 것이다."

여기까지 왔다면 풀이 방식이 상당히 다양한데, 필자는 다익스트라 기법으로 접근했다.

케이블 쌍 개수가 $10,000$개 이하이므로 사실 케이블선 비용의 종류는 최대 $10,000$개이다.

그래서, $solve(x)$를 "비용이 $x$ 이하인 간선을 제외하고 $K$개 이하의 간선만을 이용하여 $1$번 컴퓨터와 $N$번 컴퓨터를 연결할 수 있는가?" 라는 뜻으로 만들었다.

그리고 나서, $1$번 노드부터 시작해서 비용이 $x$ 이하라면 $cost$값을 그대로 두면서 pq에 집어넣고, $x$ 초과라면 $cost$값을 1 증가시키면서 pq에 집어넣었다.

그렇게 맞았습니다!! 를 받을 수 있었다.

그런데.. 사실 이 풀이는 간단히 생각하면 $O(P^2 log(N))$이라 시간 안에 안될 가능성이 있다. 

물론 저런 시간복잡도가 나오려면 정말 최악의 경우로 나와야 하지만, 가격이 $1,000,000$ 이하이고 케이블선 개수도 $10,000$개 이하이므로 사실 이론적인 최악의 경우로 나오는 것이 불가능하므로 문제가 풀린다.

다만 조금만 더 생각해 보면 더 빠른 풀이를 생각할 수 있는데, 매개변수 탐색(Parametric Search)를 사용하면 더욱 빠르게 문제를 풀 수 있다.

즉, 어차피 비용은 $1,000,000$ 이하이므로 l=$0$, r=$1,000,000$으로 두고 이분 탐색을 진행하며 $solve(mid)$가 $True$값을 내는 최소 $mid$값이 정답이라고 하고 제출하는 것이다.

이러면 시간복잡도는 $O(P log(N) log(1,000,000) )$이 되므로, 무조건 시간 안에 풀린다.

아래 코드는 매개변수 탐색 방법을 적용하여 푼 코드이다.

4. 코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

vector<vector<pair<int, int>>> v;
int n, p, k;

bool solve(int piv) {
    // piv 이하의 간선을 제외한 k개의 간선만 사용해서 1~n링크를 만들 수 있는지 여부 판단
    vector<int> cost(n+1, n);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, 1});

    while (!pq.empty()) {
        int node = pq.top().second;
        int maxx = pq.top().first;
        pq.pop();
        if (cost[node] <= maxx)  continue;
        cost[node] = maxx;

        for (int i=0; i<v[node].size(); i++) {
            if (v[node][i].second <= piv && cost[v[node][i].first] > maxx) {
                pq.push({maxx, v[node][i].first});
            }
            else if (v[node][i].second > piv && cost[v[node][i].first] > maxx + 1) {
                pq.push({maxx+1, v[node][i].first});
            }
        }
    }

    if (cost[n]<=k) return true;
    else    return false;
}

int main() {
    int ans;
    int a, b, c;
    int costs[1000001];
    memset(costs, 0, sizeof(costs));
    cin >> n >> p >> k;
    v = vector<vector<pair<int, int>>>(n+1);

    for (int i=0; i<p; i++) {
        cin >> a >> b >> c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
        costs[c]=1;
    }
    costs[0] = 1;
    ans = -1;
    int l, r, mid;
    l=0;    r=1000001;  mid=(l+r)/2;
    while (l<r) {
        mid = (l+r)/2;
        if (solve(mid)) {
            ans = mid;
            r = mid;
        }
        else {
            l = mid + 1;
        }
    }
    cout << ans;
}

5. 여담

사실 풀기 전에 "매개 변수 탐색 각인데?" 했다가 "안해도 풀리겠다" 싶어서 그냥 풀었는데, 풀고 나서 태그에 매개 변수 탐색이 박혀 있길래 매개변수 탐색으로 다시 한번 풀어봤다.

문제 출제 년도가 2008년이다보니까 $P$ 조건을 굉장히 널널하게 준 것 같은데, 아마 최근 대회였으면 $P$ 조건을 10만정도로 주지 않았을까 싶다.

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

1. 문제

- 초기에 통 개수 $N$과 통의 용량 $X$가 주어짐.

- 다음 줄에, $i$번째 용기에 담겨 있는 헤어에센스의 양 $C_i$가 $N$개 공백으로 나누어 주어짐.

- 통 $A, B$두개를 가져가면 $min(A+B+{X \over 2}, X)$만큼이 차 있는 통으로 바꿔줌.

- 용량이 꽉 찬 통을 최대 몇 개 만들 수 있는지 구해야 함.

2. 힌트

힌트 1

힌트 2

힌트 3

3. 문제 관찰 과정 및 풀이

통의 개수 $N \leq 100,000$ 이므로 시간복잡도 $O(N^2)$으로는 풀이가 불가능하다는 것을 알 수 있다.

또한, 통의 용량 $X \leq 10^{18}$이므로 크기 제한에 유의하여 long long 자료형을 사용해야 한다.

당연히도, 이미 남아 있는 통 중 꽉 찬 통이 있다면 이걸 가져가서 교체할 필요는 전혀 없으므로, 우선 꽉 찬 통은 모두 빼놓고 생각하자.

일단 관찰을 위해, 처음 생각한 것은 "아무렇게나 막 교환하면 꽉 찬 통을 몇 개까지 얻을 수 있을까?" 였다.

여기서 알 수 있었던 사실은, 남아 있던 용량과 관계 없이 통 3개로 무조건 꽉 찬 통 하나를 만들 수 있다는 것이다.

통 두개를 교체하면 최소 ${X \over 2}$만큼이 통에 차고, 그 통과 다른 통을 교체하면 최소 ${X \over 2} + {X \over 2} = X$만큼 차기 때문에, 최악으로 교환해도 통 3개만 있으면 통 하나를 가득 채울 수 있다.

그렇다면, 이 문제는 "통 두 개만을 사용하여 꽉 찬 통을 만들 수 있는 최대 개수 구하기" 문제로 바뀌었다.

통 두 개로 꽉 찬 통 하나를 만들기 위해서는 각 통에 들어 있던 헤어에센스의 양의 합이 ${X \over 2}$보다 많아야 하므로,

다시 한번 문제를 추상화하면 "남아 있는 용량이 ${X \over 2}$ 이상인 통의 쌍 개수를 최대화하여라." 로 바뀐다.

이제 남아 있는 용량이 ${X \over 2}$인 통 쌍 개수를 구하는 방법을 생각해야 한다.

그리고 조금 생각해보면, 남아 있는 용량이 $X$ 미만이지만 용량이 조금 많이 남은 통 두 개를 한번에 가져가서 교체하는 것은 용량 손해가 심해 보인다.

따라서, "용량이 많이 남아 있는 통은 용량이 적게 남은 통과 교체하는 것이 좋지 않을까?" 라는 생각을 할 수 있다.

즉, 최대한 용량이 많이 남아 있는 통과 최대한 용량이 적게 남은 통들 쌍 중에서 용량의 합이 ${X \over 2}$ 이상인 통들의 쌍을 투 포인터로 그리디하게 매칭하는 것이 최적이라는 가설을 세울 수 있다.

이제부터 이를 증명해보자.

오름차순으로 정렬 이후에, 가장 왼쪽의 통의 인덱스를 $l$, (가득 찬 통을 제외한)가장 오른쪽의 통의 인덱스를 $r$이라고 하자.

그러면, $C[l] \leq C[l+1] \leq C[l+2] \leq \dots \leq C[r-1] \leq C[r] < X$가 된다.

이 때, $C[l] + C[r] < {X \over 2}$라면 $C[l]$은 그 어떤 통과 더하더라도 ${X \over 2}$ 이상이 될 수 없으므로, $C[l]$은 반드시 통 세 개로만 교환 가능하다.

또한, $C[l] + C[r] \geq {X \over 2}$인 상태에서 $(C[l], C[r])$ 쌍 대신 $(C[l+1], C[r])$ 쌍을 선택하는 것은 최적이 아닌데, 만약 $C[l] + C[r] \geq {X \over 2}, C[l] + C[r-1] < {X \over 2}, C[l+1] + C[r-1] \geq {X \over 2}$라면 $(C[l], C[r]), (C[l+1], C[r-1])$ 쌍을 고를 수 있으나 $(C[l+1]+C[r])$ 쌍을 골라 버리면 $C[l]$은 절대 사용할 수 없는 통이 되기 때문에 무조건 손해가 된다.

따라서, 배열을 정렬한 뒤에 투 포인터로 "양쪽을 합해서 ${X \over 2}$ 이상이라면 $l++, r++$, 아니면 $l++$" 이라는 단순한 투 포인터 방식으로 정답을 구할 수 있다.

4. 코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;


int main() {
    ll n, x;
    ll c[100005];
    int ans = 0;
    
    cin >> n >> x;
    for (int i=0; i<n; i++) {
        cin >> c[i];
    }
    
    sort(c, c+n);
    
    int l=0, r=n-1;
    int left=0;
    while (c[r]>=x && r>=0) {
        r--;
        ans++;
    }
    while (l<=r) {
        if (l<r && c[r]+c[l]>=(x+1)/2) {
            ans++;
            l++;
            r--;
        }
        else {
            l++;
            left++;
        }
    }
    cout << ans+left/3;
    
}

5. 여담

사실 풀이 부분에서 $C[l] + C[r] \geq {X \over 2}$여야 한다고 했으나, 모든 $C[i]$는 정수로 입력되기 때문에 ${X \over 2}$에서 소수점은 아예 버려도 별로 상관이 없다.

사실 while()문 안에 l==r인 부분 예외 처리를 안해줘서 몇번 박았었는데, 다행히 빨리 찾아서 고쳤다.

아마 대회였으면 조금 더 심사숙고해서 정답을 박았겠지만... 그냥 문풀중이어서 대충 박아버리니까 좀 여러번 틀렸다.

연습 중에도 이런 습관은 좀 고쳐야겠다.