cdjs의 코딩 공부방

G5 | 13910 - 개업

풀이 시간: 약 10분

시도 횟수: 5회

체감 난이도: G4

풀이 쓸 의향: 下

풀이

여담: div3 버추얼 돌리기 전에 빠르게 풀어봄.

*800 | 1714A. Everyone Loves to Sleep

풀이 시간: 3분

시도 횟수: 1회

체감 난이도: B1

풀이 쓸 의향: 下

풀이

여담: 곧 있을 div3 대비? 코포 버추얼. 어차피 div3은 unrated긴 한데 재미로 해봄.

*800 | 1714B. Remove Prefix

풀이 시간: 3분

시도 횟수: 1회

체감 난이도: B1

풀이 쓸 의향: 下

풀이

여담: A보다 쉬운 B

*800 | 1714C. Minimum Varied Number

풀이 시간: 5분

시도 횟수: 1회

체감 난이도: S4?

풀이 쓸 의향: 下

풀이

여담: 사실... 그냥 손으로 다 쓴 다음에 정답 45개 복붙해서 배열에 박았음. 코드 구현보다 이게 더 빠를것 같아서..

*1600 | 1714D. Color With Occurences

풀이 시간: 22분

시도 횟수: 1회

체감 난이도: G4?

풀이 쓸 의향: 下

풀이

여담: 난이도가 무슨 ABC<<<E<D 느낌이었음... div3 난이도 맞추기가 상당히 어려워 보이긴 하는데...

*1400 | 1714E. Add Modulo 10

풀이 시간: 18분(-3분)

시도 횟수: 1회

체감 난이도: G5?

풀이 쓸 의향: 下

풀이

여담: 풀면서 재밌었던 문제. 안타깝게도 이거 풀고나서 힘이 쭉 빠져서 E는 못풀었다... ;(

P3 | 16909 - 카드 구매하기 3

풀이 시간: 1시간 + a

시도 횟수: 1회

체감 난이도: P3

풀이 쓸 의향: 下

풀이

여담: 졸린 나머지 코드를 너무 난잡하게 짰다...

G5 | 2759 - 팬케이크 뒤집기

풀이 시간: 15분

시도 횟수: 1회

체감 난이도: G5

풀이 쓸 의향: 下

풀이

여담: 코포 전 잠깐 연습용으로 풀어본 문제

이러고 나서 코포 조졌는데, 아... 너무 아깝다.... 점수가 오르긴 했는데 D번을 시간 안에 못푼게 너무 아쉬워서 빨리 다음 코포 하고싶다.

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

풀이 쓸 의향: 下

풀이

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

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

오늘은 G5~G1 랜덤 디펜스를 해봤다.

원래 순서대로 푸려고 했는데, G4랑 G2 라인 문제가 잘 안떠올라서 G5-G3-G4-G1-G2 순으로 풀렸다.

총 풀이 시간: 약 2시간 20분

G5 | 12887 - 경로 게임

시도 횟수: 1회

체감 난이도: G5

풀이 쓸 의향: 下

풀이

여담: 여기까지는 10분컷이었는데,,, :(

G3 | 19535 - ㄷㄷㄷㅈ

시도 횟수: 2회

체감 난이도: G3~G2 사이 어딘가

풀이 쓸 의향: 中

풀이

여담: DFS / BFS 문제인줄 알았는데 무조건 시간초과 난다는 것을 깨닫고 후다닥 풀이를 틀어버린 문제. 상당히 흥미로운 문제였다.

G4 | 25307 - 시루의 백화점 구경

시도 횟수: 3회

체감 난이도: G3

풀이 쓸 의향: 下

풀이

여담: 최적화를 제대로 안해서 한 번, 그냥 급하게 내다가 한 번 더 틀렸다. 원래 이렇게 오래 걸릴 문제는 아니었는데 마네킹에서 BFS를 돌릴 때 최적화하는 방법이 뭔가 머리에서 안떠올랐다. 피곤한 날엔 코딩하지 말아야지...

G1 | 21320 - 순간이동 여행

시도 횟수: 1회

체감 난이도: G1

풀이 쓸 의향: 中

풀이

여담: 풀이가 꽤 재밌고 dp 점화식 구하는 과정이 흥미로웠다.

G2 | 1797 - 균형잡힌 줄서기

시도 횟수: 2회

체감 난이도: G2

풀이 쓸 의향: 下

풀이

여담: 처음에 prefix sum이라고 잘 생각했다가 갑자기 턱 막혀서 위의 G1 문제로 넘어갔었다.

DP로 해결되지 않을까 하는 마음에 DP 점화식을 세워보려던게 패착이었던 것 같은데, 사실 이 문제에서 prefix sum을 안쓰면 딱히 할 수 있는게 없어 보였음에도 부분합 풀이를 치워두고 DP 풀이로는 왜 갔던걸까....

P4 | 17408 - 수열과 쿼리 24

풀이 시간: 약 25분

시도 횟수: 4회

체감 난이도: P4 날먹

풀이 쓸 의향: 下

풀이

여담: 이날 코포치느라 글도 못쓰고 문제도 별로 못풀었는데, 코포도 조져서 슬프다,,, :(