cdjs의 코딩 공부방

P4 | 8903 - 장비

풀이 시간: 40분

시도 횟수: 2회

체감 난이도: P4

풀이 쓸 의향: 下

풀이

여담: 저번에 풀었던 Baseball Watching 문제와 비슷한 브루트 포싱 문제. 왠진 모르겠는데 이런 문제 참 좋다.. 뭔가 색다른 느낌

https://www.acmicpc.net/problem/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로 풀고 있었다. 사실 시간 복잡도 자체는 비슷해서 딱히 상관은 없고, 그냥 새로운 풀이 정도의 느낌.

P5 | 23760 - 까다로운 아이들과 선물 상자

풀이 시간: 20분+25분

시도 횟수: 4회

체감 난이도:  P5

풀이 쓸 의향: 下

풀이

여담: 풀이 시간이 20분 + 25분인 이유는 처음에 문제를 잘못 읽었기 때문... 1번 아이부터 M번 아이까지 순서대로 선물을 가져가는게 아니라, 최적의 순서로 아이들을 놓았을 경우 가능한지를 묻는 문제인줄 알았다. 풀고 나서 예제 넣어봤는데 답이 이상하게 나와서 다시 보니까 순서대로 놓는거였다.... 아니 최적의 순서로 아이들 놓는 문제도 풀이 재밌고 좋은데 ;(

시도 횟수 4회는... 빠르게 틀린 이유 3개 찾아서 파바박 넣었다. 아니 이럴거면 제출 전에 좀 보지....

P3 | 13134 - Baseball Watching

풀이 시간: 1시간 30분

시도 횟수: 1회

체감 난이도: P3

풀이 쓸 의향: 中

풀이

여담: 풀이 중간에 풀이를 한번 떠올렸다가 갑자기 이상한 코드를 짜기 시작하더니 미궁으로 빠져버린 요상한 케이스... 근데 문제 아이디어가 참 마음에 들었다. 일반적인 최적화 문제만 풀다 이런 문제 푸니까 머리가 어지럽다...

P5 | 19580 - 마스크가 필요해

풀이 시간: 10분

시도 횟수: 1회

체감 난이도: P5?

풀이 쓸 의향: 中

풀이

여담: 내가 좋아하는 유형의 문제라 상당히 빠르게 풀 수 있었던 것 같다. 그 리 디 조 아

사실 풀이가 처음 머리에 딱 박혀서 빠르게 풀긴 했지만, 구현하는 방식도 까다롭기도 하고 머리에 풀이가 빠르게 안박혔으면 풀기 많이 힘들었을 듯 하다.

G5 | 25513 - 빠른 오름차순 숫자 탐색

풀이 시간: 10분

시도 횟수: 1회

체감 난이도: G5

풀이 쓸 의향: 下

풀이

여담: 골드 조지기 시작!

G4 | 4179 - 불!

풀이 시간: 25분

시도 횟수: 6회

체감 난이도: G3

풀이 쓸 의향: 下

풀이

여담: 어제의 구현 까다로운 BFS에 이은 두 번째 구현 까다로운 BFS. 음... 내가 이런 문제쪽에 약한가보다.

G3 | 14595 - 동방 프로젝트

풀이 시간: 7분

시도 횟수: 1회

체감 난이도: G4

풀이 쓸 의향: 下

풀이

여담: 자칫 유니온&파인드를 구현해서 풀어야 할 문제처럼 보일 수 있지만, 그냥 정렬하거나 위의 풀이처럼 풀면 쉽게 풀린다.

G2 | 17942 - 알고리즘 공부

풀이 시간: 1시간

시도 횟수: 11회

체감 난이도: G2

풀이 쓸 의향: 下

풀이

여담: 처음엔 매개변수 탐색으로 풀다가, 왜인지 모른 맞왜틀 끝에 그냥 빠르게 구현 수정해서 매개변수 탐색 없이 내니까 됐음.

아니 근데 매개변수 탐색 있이 풀어도 똑같은 코드인데 왜틀렸지...??? 하고 있었는데 별 미친실수를 다했었네..... 미친건가 진짜?