cdjs의 코딩 공부방

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인 부분 예외 처리를 안해줘서 몇번 박았었는데, 다행히 빨리 찾아서 고쳤다.

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

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