[백준] 6132 - 전화선 힌트, 풀이 및 코드 (C++)

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

6132번: 전화선

 

* 해당 풀이는 정해와는 다른 풀이입니다.

 

1. 문제

- $N(\leq 100,000$)개의 전신주의 높이 $H_i(\leq 100)$와 정수 $C(\leq 100)$가 주어진다.

- 총 비용은 $C * |두 전신주의 높이 차|$의 합으로 이루어진다.

- 전신주의 높이를 $X$만큼 높이면 비용은 $X^2$만큼 늘어난다.

- 가능한 비용의 최솟값을 구하시오.

 

 

2. 힌트

 

힌트 1

당연하게도, 높이가 이미 최대인 전신주의 높이는 올릴 필요가 전혀 없다. 또한, 문제 조건에 의해, 대부분의 경우 높이가 최소인 전신주의 높이는 올리는 것이 최적이다.

 

힌트 2

높이가 최소인 전신주의 왼쪽/오른쪽 전신주의 높이 중 하나라도 그 전신주의 높이보다 낮거나 같으면, 높이가 최소인 전신주의 높이를 올리지 않는 것이 최적일 가능성이 있다. 이 때 전신주의 높이를 올려야할지 말아야할지는 어떻게 선택해야 할까?

 

힌트 3

어떤 전신주의 좌/우 높이 중 하나라도 작은 것이 있다면, 반드시 더 작은 전신주를 먼저 올리고 보는 것이 좋다.

 

 

3. 문제 관찰 과정 및 풀이

 

처음 문제를 봤을 땐, 정말 답도 없게 느껴졌다. 뭔가 수학 문제 같기도 하고... 어떤 전신주를 올려야 최적인지에 대해 고민해봤다.

일단 처음 관찰했던 것은, 당연히도 높이가 최대인 전신주는 처음부터 끝까지 건드릴 일이 전혀 없다는 것이다.

해당 전신주는 높여봤자 이득 보는것이 전혀 없기 때문이다.

그렇다면 최소인 경우는 어떨까? 거의 대부분의 경우에는 1은 올리는 것이 최적이지만, 최소인 것이 여러개 동시에 있다면 해당 전신주를 올리지 않는 것이 최적일 수도 있다.

왜냐하면 이웃한 전신주 중 해당 전신주와 높이가 동일한 것이 하나라도 존재한다면 해당 전신주를 높였을 때 얻는 비용 이득 없이 $(X+1)^2 - X^2$만큼의 손해만 보기 때문이다.

 

여기서 중요한 관찰이 이미 등장했는데, 사실 못보고 지나쳤다. 잠시 DP를 생각하다가, 저주받은 DP 실력에 의해 한번 밀려나가 풀이 노트를 뚫어져라 쳐다보던 중, 위의 노트를 다시 보았다.

이웃한 전신주 중 하나라도 높이가 같거나 낮은게 있다면 그 즉시에는 얻는 비용 이득 없이 $(X+1)^2 - X^2$만큼의 손해만 본다..?

그런데 그렇다면 이웃한 전신주들 중 하나라도 높이가 같거나 낮다면 해당 전신주를 올리지 않는것이 최적인가? 하면 그것은 아닌 것이, 해당 전신주와 높이가 같거나 낮은 전신주를 동시에 올리면 비용이 더 낮아질 수도 있기 때문이다.

 

여기서 드는 의문. 그렇다면 높이가 같은 전신주 두 개가 서로 붙어 있으면, 동시에 높이를 높이는 것이 최적일까?

그리고 잘 생각해 보면, 두 전신주 중 하나의 높이를 올리지 않으면 위에서 언급한 바와 같이 아무런 비용 이득 없이 $(X+1)^2 - X^2$만큼의 손해만 보게 되므로, 당연히 이는 사실이라고 할 수 있다.

 

또한 중요한 관찰이 하나 더 있는데, 작은 전신주부터 차례대로 그리디하게 높이를 올려보는 것이 반드시 최적이라는 것이다.

즉, 작은 전신주부터 "지금 올렸을 때 당장 비용이 줄어든다면 올리고, 아니면 더 이상 올리지 않는다" 라는 것이다.

작은 전신주 입장에서 보았을 때, 양 옆의 전신주가 얼마나 더 높아지는지와 큰 관계 없이 어차피 높이 1 차이당 $C$만큼의 비용 손해를 보게 된다.

그러나, "이웃한 전신주 중 하나라도 해당 전신주보다 작은 것이 있다면 올리지 않는 것이 최적이다" 라는 사실을 잘 생각해 보자.

만약 현재 비용 손해를 감수하고 해당 전신주를 올렸더라도, 어차피 양 옆의 전신주가 해당 전신주보다 크다면 어차피 해당 전신주로 인한 비용 이득은 더 이상 존재하지 않는다. (어떤 전신주의 비용 이득 / 손해는 전적으로 이웃한 전신주에만 관계가 있기 때문이다)

 

따라서, 가장 작은 높이의 연속된 구간을 그리디하게 하나씩 올려보며 비용 이득이 생기면 해당 구간의 높이를 올리고, 아니면 그대로 두는 방식으로 코드를 구현하면 된다.

구현 방식은 여러가지겠지만, 필자는 pq<tuple<int, int, int>>를 사용하여 해결하였다. 만약 pq.top()이 지금 막 올리려는 높이와 같다면 구간을 합쳐주는 방식으로 구현하면, 약 $NlgN$ 안에 해결 가능하다.

또한, 높이는 최대 $H_{max}$까지만 올리므로, 위의 연산을 $H_{max}$만큼 반복하면 총 시간 복잡도는 약 $NH_{max}lgN$ 이다.

제한 시간이 1초라는 점을 감안하면 조금 빡빡하다 생각될 수 있지만, 어차피 올리는 높이가 $\sqrt{2C}$만 넘어가도 무조건 올리지 않는 것이 최적이므로 최악의 경우에도 $\sqrt{2C}NlgN$ 정도의 시간 안에 가능하며, 이는 굉장히 널널한 시간이다.

 

4. 코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    int n, c, h[100005], a[100005];
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq;
    cin >> n >> c;
    int p = 0;
    for (int i=1; i<=n; i++) {
        cin >> h[i];
        a[i] = h[i];
        pq.push({h[i], i, i});
    }
    
    for (int i=1; i<n; i++) {
        p += abs(h[i+1] - h[i]) * c;
    }
    while (!pq.empty()) {
        int val, l, r;
        tie(val, l, r) = pq.top();
        pq.pop();
        
        while (!pq.empty() && val == get<0>(pq.top()) && get<1>(pq.top()) == r+1) {
            r = get<2>(pq.top());
            pq.pop();
        }
        
        
        int penalty = 0;
        for (int i=l; i<=r; i++) {
            penalty += (val + 1 - h[i]) * (val + 1 - h[i]) - (val - h[i]) * (val - h[i]);
        }
        if (l!=1)   penalty += (a[l-1] > a[l]) ? -c : c;
        if (r!=n)   penalty += (a[r+1] > a[r]) ? -c : c;
        if (penalty < 0) {
            p += penalty;
            pq.push({val+1, l, r});
            for (int i=l; i<=r; i++)    a[i] = val+1;
        }
    }
    
    cout << p;
}

5. 여담

비록 정해는 아니지만, 이런 그리디 아이디어 자체는 상당히 훌륭하고 재밌는 아이디어인 것 같다. 풀자 마자 글을 쓰고 싶었던 문제 중 하나.

정해 풀이는 DP 풀이인것 같은데, 풀고 나서 죄다 DP 태그가 박혀 있길래 USACO editorial까지 찾아보니까 거기서도 dp로 풀고 있었다. 사실 시간 복잡도 자체는 비슷해서 딱히 상관은 없고, 그냥 새로운 풀이 정도의 느낌.