cdjs의 코딩 공부방

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

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

1. 문제

- $N$명의 사람들이 마피아 게임을 진행한다.

- 각 사람들이 마피아일것 같은 사람을 투표하게 되는데, 시민은 자신을 제외한 다른 사람 아무나 투표하고, 마피아는 시민 중 한 명에게 투표한다.

- 마피아일 수 있는 사람 수의 최대값을 출력하라.

2. 힌트

힌트 1

힌트 2

힌트 3

3. 문제 관찰 과정 및 풀이

3-1. 문제 관찰 과정

문제를 처음 봤을 때, 솔직히 조금 어지러웠다. 문제 지문이 살짝 이해하기 힘든 점도 있기는 했지만, 그보다도 대체 문제 풀이를 어떻게 시작해야 할지 감도 안잡혔기 때문이다.

조금 생각하다 보니, 참가자의 투표를 유향 그래프로 나타내어 그래프를 직접 그려보면 문제 상황 자체를 쉽게 이해할 수 있다 생각이 들어 그림판을 켜서 예제 입력을 직접 그리며 관찰해 보았다.

"마피아는 서로 마피아를 투표하지 않는다" 라는 것은, 그래프가 a->b로 연결되어 있을 때 a번 사람이 마피아라면 b번 사람은 마피아일 수 없다는 것을 의미한다.

그런데, 어차피 a->b로 연결되어 a번 사람과 b번 사람이 동시에 마피아가 될 수 없다면 그래프를 유향 그래프로 그리는 것이 오히려 불편해지기 때문에, 무향 그래프로 바꾸어 생각해 보았다.

이렇게 무향 그래프로 바꾸고 나면 "서로 이웃하지 않는 노드들을 최대한 많이 선택할 때, 그 노드들의 개수를 구하여라" 라고 문제를 변환하여 생각할 수 있다.

처음에는 DP 문제일까 하고 고민해 보았는데, 어떻게 구현해도 시간 안에 예쁘게 구현될 것 같지 않아서 때려쳤다.

그렇게 계속 관찰하다가, "일단 반드시 골랐을 때 이득인 노드가 있을까?" 라는 생각으로 그래프를 살펴보았다.

가장 처음에는 연결된 개수가 가장 작은 것을 먼저 고르면 되는 그리디 문제인가 고민해 보았지만, 바로 반례를 찾아 폐기되었다.

그런데 반례를 만들다가 a->b->c로 일직선으로 (즉, 옆으로 새는 길 없이) 연결된 형태이며 a, b번 노드가 둘 다 단말 노드라면 b보다는 a를 고르는 것이 최적이라는 사실을 발견했다.

이를 조금 더 확장하여 문제를 해결해 보자.

3-2. 문제 풀이

각 정점을 사람의 번호, 간선은 서로가 투표했는지 여부에 따라 무향 그래프를 하나 생성한다.

그렇다면 문제가 "서로 이웃하지 않는 노드들을 최대한 많이 선택할 때, 그 노드들의 개수를 구하여라" 로 치환된다.

이 때, 반드시 단말 노드를 가장 먼저 고르는 것이 최적이라는 사실을 관찰을 통해 짐작할 수 있다.

이유는 간단한데, 단말 노드의 경우 간선이 단 하나만 연결되어 있으므로 해당 노드를 골랐을 때 고르지 못하게 되는 노드는 단 하나만 생긴다.

그런데 단말 노드 대신 고르지 못하게 되는 다른 노드를 고르게 되면 반드시 단말 노드를 고른 것보다 고를 수 있는 노드 수가 항상 같거나 적으므로, 단말 노드를 고르는 것이 더 최적해라는 것을 알 수 있다.

또한, 단말 노드가 존재하지 않을 때까지 노드를 고르면 나머지 그래프들은 전부 거대한 사이클 하나로 이루어진 그래프가 되는데, 사이클 하나로 이루어진 그래프에서는 반드시 (노드 개수 / 2) 만큼의 노드를 고를 수 있으니 각 사이클을 DFS로 돌며 크기를 확인하고 값을 더해주면 된다.

주의할 점은, 이 문제의 경우 그래프 하나가 아니라 끊어져 있는 서로 다른 여러 그래프가 나올 수 있으므로 사이클 크기 처리를 해 줄때 각 그래프에 대해 한 번씩 전부 돌며 연산해주어야 한다.

4. 코드

너무 신난 상태로 코드를 짜서 그런지 코드가 많이 더럽다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

vector<int> visited;
vector<vector<int>> v;

int dfs(int node, int x) {
    visited[node] = 1;
    for (int i=0; i<v[node].size(); i++) {
        if (visited[v[node][i]])    continue;
        return dfs(v[node][i], x+1);
    }
    return x;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    int n;
    int a[500005];
    int cnt[500005];
    int ans = 0;
    memset(cnt, 0, sizeof(cnt));
    cin >> n;
    
    v = vector<vector<int>>(n+1);
    visited = vector<int>(n+1, 0);
    
    for (int i=1; i<=n; i++) {
        cin >> a[i];
        if (a[i] < i && a[a[i]] == i) {	// 서로가 서로를 지목한 경우;
            continue;
        }
        v[i].push_back(a[i]);
        v[a[i]].push_back(i);
        cnt[a[i]]++;	// 연결된 간선 개수
        cnt[i]++;
    }
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    for (int i=1; i<=n; i++) {
        pq.push({cnt[i], i});
    }
    
    while (!pq.empty()) {
        int sz = pq.top().first;
        int node = pq.top().second;
        pq.pop();
        if (visited[node])  continue;
        if (sz>1)  break;
        
        ans++;
        visited[node] = 1;
        for (int i=0; i<v[node].size(); i++) {
            int nnode = v[node][i];
            if (visited[nnode]) continue;
            visited[nnode] = 1;
            for (int j=0; j<v[nnode].size(); j++) {
                if (visited[v[nnode][j]])   continue;
                cnt[v[nnode][j]]--;
                pq.push({cnt[v[nnode][j]], v[nnode][j]});
            }
        }
    }
    
    for (int i=0; i<n; i++) {
        if (visited[i]) continue;
        ans += dfs(i, 1) / 2;
    }
    
    cout << ans;
}

5. 여담

오랜만에 정말 마음에 드는 문제를 풀었다. 관찰 과정부터 풀이 구현까지 전부 즐겁게 해결한 문제.

태그 중에 분리 집합이 있는 것을 보아하니 분리 집합으로도 풀 수 있는 모양이다.

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

1. 문제

- dig라는 함수를 다음과 같이 정의하자.

$dig(x) = x(0 \leq x \leq 9)$

$\cdot dig(x) = dig(x의  모든  자리수의  합) (x \geq 10)$

- 각 테스트케이스에 $M$, $K$가 주어진다. ($M \leq 1,000 , K \leq 10^9$)

- 초기에 (0, 0)에서 북쪽을 바라보고 있으며 초기값이 1인 골드 넘버 대해, $dig(골드 넘버)$만큼 앞으로 가고 90도 오른쪽으로 회전한 뒤, 골드 넘버에 $M$을 곱하는 것을 $K$회 반복한다.

- 위 작업을 실시했을 때 최종 위치는 어디인가?

2. 힌트

힌트 1

힌트 2

힌트 3

3. 문제 관찰 과정 및 풀이

3-1. 문제 관찰 과정 및 풀이

처음 문제를 보면, $K$의 값이 너무나도 크기 때문에 직접 돌려보는 것은 아예 불가능하다는 것을 파악할 수 있다.

따라서, 반드시 반복 횟수를 줄일 수 있는 수학적 방법이 존재함을 고려할 수 있다.

우선 첫 번째 예제 케이스를 직접 계산해 보면서 규칙을 찾아보자.

$K=5, M=2$인 상황에서 골드 넘버는 $1, 2, 4, 8, 16$이 되고, $dig(x) = 1, 2, 4, 8, 7$이 된다.

뭔가 부족하니까 K를 늘려서 조금 더 관찰해 보자.

골드 넘버가 $1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024$일때, $dig(x) = 1, 2, 4, 8, 7, 5, 1, 2, 4, 8, 7$이 된다.

...왠지 모르게 숫자가 반복된다는 점을 파악할 수 있지만, 이것만으로는 풀이가 불완전하다.

반복이 일어난다면 어째서 반복이 일어나는지를 파악해야 하므로, 우선 $K$를 획기적으로 줄일 수 있는 방법이 있다는 믿음을 가지고 삽질을 시작하자.

우선 $dig$의 정의는 숫자 각 자리의 합으로 이루어져 있다는 것을 확인할 수 있다.

그러면 $dig(x)$와 $dig(x*M)$의 관계성을 분석하기 위해선, $x$와 $x*M$의 각 자리의 합을 생각해야 한다.

$x$의 각 자리수를 분해하여 $x$를 $a + 10b + 100c + \dots $라고 하면, $x*M = a*M + b*M + c*M + \dots$ 라는 사실은 쉽게 확인할 수 있다.

그런데 $dig(x) = a + b + c + \dots$이고, $x*M = a*M + b*M + c*M + \dots$이므로 $dig(dig(x)*M) = dig(x*M)$이라는 사실을 확인할 수 있다!

또한, 위 성질을 연장하여 $dig(dig(dig(x)*M)*M) = dig(dig(x*M)*M)$라는것 또한 알 수 있으므로, 어떤 $x$에 대해서도 $dig(x*M^y)$의 계산에서 $M$을 $K$번 곱하지 않고도 구할 수 있음을 확인할 수 있다.

다음은 $dig(x)$의 값이 반드시 0 이상 9 이하라는 점에서 주목해 보자.

$dig(dig(x)*M) = dig(x*M)$의 성질에서 파악 가능하듯, $dig(x*M)$의 값은 $dig(x)$값만 알아도 구할 수 있는데, $dig(x)$의 값은 0 이상 9 이하이므로 어떤 수 $M$에 대해 $dig(x*M)$의 값은 $dig(x)$의 열가지 경우의 수에 대해서만 결정된다.

(TMI: 물론 $dig(x)$의 정의에 의해 $dig(x)$가 0이 되는 일은 없어서 아홉 가지 경우의 수밖에 없긴 하다)

가령, $M=2$에 대해 그 어떤 $x$에 대해서도 $dig(x)=1$이면 $dig(x*M)=2$, $dig(x)=5$이면 $dig(x*M)=1$과 같이 결정된다는 것이다.

이에 따라 반드시 $dig(x) = dig(x*M^y)$인 지점이 생기게 되므로 반복하는 구간이 생기게 되고, 이 주기는 비둘기집의 원리에 의해 최대 10이 된다.

이제 이 주기에 따라 $K$값을 줄여주는 구현을 하면 되는데, 이 구현을 생각하기가 조금 까다로울 수 있다.

필자의 경우, queue에 값을 계속 넣어주다가 이미 들어온 적 있는 값이 queue에 들어오면 해당 값이 front에 올때까지 pop해준 뒤, $K %= 해당 queue의 길이 * 4$ 연산으로 $K$값을 줄여주었다.

이렇게만 줄이더라도 queue의 길이는 최대 10이라는 사실을 파악했으므로 $K$는 40 이하가 되고, 40번까지는 충분히 브루트 포스로 돌릴 수 있으므로 그대로 구현하면 된다.

4. 코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int dig(int x) {
    if (x<10)   return x;
    int sum = 0;
    while (x>0) {
        sum += x%10;
        x/=10;
    }
    return dig(sum);
}
int main() {
    int t;
    cin >> t;
    while (t--) {
        queue<int> q;
        int k, m;
        int y=0, x=0;
        int dir = 0;
        cin >> k >> m;
        vector<int> visited(10, 0);
        int num = 1;
        while (k>0) {
            if (visited[num]) {
                while (q.front() != num) {
                    q.pop();
                }
                k%=(4*q.size());
                if (k==0)   break;
            }
            visited[num] = 1;
            q.push(num);
            switch(dir) {
                case 0:
                    y+=num;
                    break;
                case 1:
                    x+=num;
                    break;
                case 2:
                    y-=num;
                    break;
                case 3:
                    x-=num;
                    break;
            }
            k--;
            num = dig(num*m);
            dir = (dir+1)%4;
        }
        cout << x << " " << y << "\n";
    }
}

5. 여담

처음에 $K$ 나머지 연산할 때 0이어도 계속 진행되게 코드를 구현해서 WA를 띄웠었다.

대회에서 신나게 풀어놓고 저렇게 실수해서 패널티 쌓이면 상당히 슬프겠는데....

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

! 본 게시글에서 설명하는 풀이는 (아마도?) 문제가 의도한 정해와 다른 방식으로 푼 풀이입니다.

1. 문제

- $N$ ($1 \leq N \leq 100$)개의 섬과 $M$ ($1 \leq M \leq 1,000$)개의 다리가 주어진다.

- 각 다리가 주어질 때, 각 다리가 버틸 수 있는 보석의 무게 제한 $c$($1 \leq c \leq 100$)이 함께 주어진다.

- 섬들 중, $K$ ($1 \leq K \leq 14$)개의 섬에는 보석이 있다.

- 시작 지점으로 가지고 돌아올 수 있는 최대 보석 개수를 구하여라.

2. 힌트

힌트 1

힌트 2

힌트 3

3. 문제 관찰 과정 및 풀이

일단 문제를 처음 봤을 때, 뭔가 다른 그래프 문제에 비해서는 $N, M, K$의 크기 제한이 상당히 작게 설정되어 있다는 사실을 확인했다.

보통 이런 경우는 특정 풀이를 의도하고 낸 문제인 경우가 많지만, 처음에는 딱히 크기 제한에 신경쓰지 않고 풀이를 생각해 보았다.

우선 이 문제는 여타 그래프 문제와 다르게 각 다리가 가지는 무게 제한만 존재하며 섬과 다리를 여러 번 방문해도 되므로 각 섬에 도달 가능성 여부는 어떤 경로로 통해 가는지와 관계 없이 경로 상에 가장 무게 제한이 작은 다리와만 관계가 있다.

즉, 각 섬에 도달하는 최적의 경로는 시작 섬에서 해당 섬으로 가는 모든 경로들 중, 최소 무게 제한이 최대인 경로이다.

어차피 출발은 시작 섬에서만 하므로, 우선 시작 섬에서 보석이 있는 섬(이하 보석 섬이라고 통칭)들로 갈 때 들고다닐 수 있는 최대 보석 개수를 전부 구해보기로 했다.

시작 섬에서 다른 섬으로 갈 때 들고다닐 수 있는 최대 보석 개수는 최소 스패닝 트리나 다익스트라의 구현을 살짝 바꿔서, pq에 시작 노드에서 해당 노드로 가는 간선 가중치의 합을 저장하는 것이 아니라, $min($현재 노드로 올때까지의 최소 무게 제한$)$을 저장해 두면 쉽게 구할 수 있다.

여기서 핵심 아이디어는, "어차피 언젠가는 시작 섬으로 돌아와야 한다"는 것이다.

아무리 좋은 경로를 타고 많은 보석을 모았어도, 결국 그 보석들을 들고 시작 섬으로 돌아갈 수 있는 경로가 존재해야 한다는 것이다.

너무나도 당연한 소리같아 보이지만, 위 아이디어를 각각의 보석 섬에 적용시켜보면,

"어떤 보석 섬에 있는 보석을 줍기 위해선, 시작 점과 해당 보석 섬 사이 경로의 최대 무게 제한이 지금 가지고 있는 보석보다는 커야 한다"는 말과 동치이기 때문이다!

즉, 각 보석 섬에서 보석을 주울지 말지는 오로지 시작 섬과 해당 보석 섬 사이의 무게 제한에만 연관이 있다는 소리이다.

증명 겸 부연설명

여기까지 생각이 도달했으면 최대 보석 개수를 구하는 일은 매우 쉽다.

단순히 시작 섬과 각 보석 섬 사이의 무게 제한이 최소인 것부터 차례대로 그리디하게 보석을 가져올 수 있는지 판단하면 되기 때문이다.

여기서 주의할 점은, 시작 섬에 있는 보석은 어떤 무게 제한과도 상관 없이 반드시 주울 수 있으므로, 해당 경우에 대한 예외 처리를 해 주어야 한다는 것이다.

4. 코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main() {
    int n, m, k;
    vector<vector<pair<int, int>>> v;
    int x;
    cin >> n >> m >> k;

    vector<int> gem(n+1, 0);
    for (int i=0; i<k; i++) {
        cin >> x;
        gem[x] = 1;
    }
    
    v = vector<vector<pair<int, int>>>(n+1);

    int a, b, c;
    for (int i=0; i<m; i++) {
        cin >> a >> b >> c;
        v[a].push_back({c, b});
        v[b].push_back({c, a});
    }

    priority_queue<pair<int, int>> pq;
    vector<int> maxw(n+1, 0);
    for (int i=0; i<v[1].size(); i++)   pq.push({v[1][i].first, v[1][i].second});

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

        for (int i=0; i<v[node].size(); i++) {
            if (maxw[v[node][i].second])   continue;
            pq.push({min(dist, v[node][i].first), v[node][i].second});
        }
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> lpq;
    for (int i=1; i<=n; i++) {
        if (maxw[i]==0) continue;
        lpq.push({maxw[i], i});
    }

    int ans = 0;
    while (!lpq.empty()) {
        int dist = lpq.top().first;
        int node = lpq.top().second;
        lpq.pop();
        if (node == 1 || gem[node] == 0)  continue;
        if (dist <= ans)    continue;
        ans++;
    }
    if (gem[1]==1)  ans++;

    cout << ans;
}

5. 여담

사실 풀고 나서 "왜 이게 골드 1이지?" 에서 한 번 놀라고, "왜 이게 비트마스킹이지?" 에 두 번 놀랐다.

아마 K 범위가 수상하게 작게 주어져서 다들 비트마스킹으로 생각이 갔던 것 같은데, 차라리 K 범위가 아예 컸으면 난이도가 더 내려가지 않았을까?

가끔 문제를 보자마자 풀이가 떠오르는 문제들이 있는데, 이 문제가 바로 그런 문제였다.

힌트와 문제 풀이 부분이 다른 문제들에 비해 좀 빈약한 이유도, 어떤 대단한 생각들이나 시도를 하면서 얻어낸 결과가 아니라 그냥 "그래 보이는데 증명해볼까?" 하다가 나온 것이라...

https://acmicpc.net/problem/1185

1. 문제

- $N$개의 나라에 방문하는 비용과, $P$개의 도로들의 통행 비용이 주어진다.

- $N$개의 나라를 모두 연결하도록 $N-1$개의 도로만을 남긴 상태로, 나라에 방문하는 비용과 도로들을 이용하는 비용의 최솟값을 구하여라.

- 이때, 여행을 시작하는 나라는 아무렇게나 정할 수 있으나 끝내는 나라는 반드시 시작하는 나라여야만 한다. (즉, 시작 나라로 돌아와야 한다.)

2. 힌트

힌트 1

힌트 2

힌트 3

3. 문제 관찰 과정

문제를 처음 보자마자 이런 생각이 들었다.

"$N$이 $10,000$까지인데 시작 나라도 정해주지 않았으면서, $N-1$개의 도로만을 남기라고? 시간 안에 되나?"

만약 시작 나라를 하나씩 정하면서 각각의 최소 비용을 구하는 방식으로 문제를 해결하고자 하면, 최소 비용을 구하는 시간복잡도가 많아봤자 $O(logN)$ 수준이어야 하는데, 도로 개수가 $N-1$개이므로 모든 도로를 돌아보지도 않으면서 최소 비용을 $O(logN)$ 안에 구하는 것은 불가능해 보인다.

따라서, 뭔가 문제 속에 숨겨진 관찰을 통해 문제를 해결해야 한다는 뜻이다.

일단 가장 처음 한 가정은 "그냥 비용이 작은 도로만 고르면 안되나?" 였다.

물론 당연히 틀린 가정이라고 생각했지만, 이런 틀린 가정을 부수는 반례를 생각해보며 문제의 관찰을 더욱 다채롭게 할 수 있다고 생각해 반례를 생각해 보았다.

위 반례는 단순하게, "방문 비용이 높은 나라를 여러 번 방문할 수 밖에 없이 도로를 연결하는 경우"였다. 그런데 그렇다면 "방문 비용이 높은 나라를 여러 번 방문할 수 밖에 없는"경우는 과연 어떤 경우일까?

사실 딱 여기까지만 생각하고 머리가 어질어질해지는 바람에 일단 메모장에 적어만 두고 간단한 예시들을 작성해 보았다.

가장 단순한 예시는 나라가 오로지 두 개 이고 사이클이 생기는 도로가 생겼을 경우였는데, 이 경우에는 자명히 도로의 비용만을 고려하면 최고의 답안이 나오므로 무시하고 다음으로 넘어갔다.

다음 예시는 나라가 세 개이고 사이클이 생기는 도로가 있을 경우였는데, 이 경우에는 도로를 단 하나만 없애야 총 2개의 도로로 모든 나라를 연결할 수 있었다.

각 정점을 1, 2, 3이라고 했을 때, 간선을 잘랐을 때 다음과 같은 경우만 나온다.

1-2-3 (2가 중앙에 있는 경우),  1-3-2 (3이 중앙에 있는 경우), 2-1-3(1이 중앙에 있는 경우)

일단 단순하게 생각하기 위해 첫 번째 1-2-3인 경우만 보고 생각해 보았다.

시작 나라가 1번 나라인 경우, 1-2 간선은 2회, 2-3간선은 2회 타고, 1번 나라는 2회, 2번 나라는 2회, 3번 나라는 1회 방문하게 된다.

시작 나라가 2번 나라인 경우, 1-2 간선은 2회, 2-3간선은 2회 타고, 1번 나라는 1회, 2번 나라는 3회, 3번 나라는 1회 방문하게 된다.

시작 나라가 3번 나라인 경우, 1-2 간선은 2회, 2-3간선은 2회 타고, 1번 나라는 1회, 2번 나라는 2회, 3번 나라는 2회 방문하게 된다.

뭔가 이렇게 나열하고 보니 특이한 점을 찾을 수 있었다.

우선, 모든 도로는 시작 나라를 어떻게 잡는지와 관계 없이 오로지 두 번씩만 타고 있었고, 나라 방문 횟수는 시작하는 나라는 한 번 더 방문하며, 중앙에 있는 나라는 다른 나라보다 조금 더 방문하는 것 같아 보였다.

이 과정 속에서, "혹시 모든 도로는 무조건 두 번씩 이용해야 하나?"와, "나라를 많이 방문하게 되는 경우가 다른 나라 사이에 껴 있는 경우인건가?" 라는 생각을 하게 되었다.

4. 풀이

우선 나라가 $N$개이고, 도로가 최적으로 $N-1$개로 선택되어 있으며 시작 나라도 이미 최적으로 결정되었다고 가정하자.

즉, 이미 모든 것이 정해진 상태에서 그냥 모든 도시를 방문하는 최소 비용만 계산해 보자는 뜻이다.

우선 도로를 이용하는 데 필요한 비용을 간단하게 계산해 보자.

도로가 $N-1$개 뿐이므로, 관찰을 통해 다음과 같은 성질들을 확인할 수 있다.

    - 모든 도로를 전부 다 최소한 한 번씩은 사용해야만 한다. (각 나라를 연결하는 경로가 유일하기 때문)

    - 시작 나라를 $S$라 했을 때, 모든 나라를 순회하고 $S$로 돌아오려면 반드시 다른 모든 나라에 들어갔다 나오는 동작을 해야만 한다. 따라서, 모든 도로는 최소한 두 번씩은 사용해야만 한다.

    - 어떤 나라를 방문하기 위해 도로를 사용한 뒤 다시 돌아오기 위해 그 도로를 사용하여 총 2회 사용했다면, 더 이상은 그 도로를 사용할 필요가 없다. 더 이상 그 도로를 사용해서 방문해야 하는 나라가 없어지기 때문이다.

따라서, 시작 나라가 어디에 있든지간에 모든 도로는 반드시 단 두 번만 사용하게 된다.

그렇다면 나라를 방문하는 데 필요한 비용은 어떻게 계산할 수 있을까?

만약 시작 나라 $S$에서 나라$A$로 연결하는 도로 하나와, 나라$A$에서 나라 $B, C, D$로 이동할 수 있는 도로가 하나씩 존재한다면, (즉 $(S, A), (A, B), (A, C), (A, D)$를 연결하는 도로가 존재한다면) 필연적으로 각 도로를 최소 한 번씩은 사용해야만 한다.

그렇기 때문에 나라 $A$에서 나라$B$로 이동한 뒤에 다시 나라 $C, D$로 이동하기 위해선 반드시 나라 $A$를 재방문해야 하고, 나라 $A$에서 나라 $C$로 이동한 뒤에 다시 나라 $D$로 이동하기 위해선 다시 반드시 나라 $A$를 재방문해야 한다.

또한, 다시 시작 나라$S$로 돌아가야 하므로 나라 $D$를 방문한 뒤에 다시 나라 $A$로 돌아가서 나라 $S$로 돌아가야만 한다.

이 때, $A$를 방문하는 횟수는, 시작 나라 $S$에서 $A$로, $B$에서 $A$로, $C$에서 $A$로, $D$에서 $A$로 방문하는 총 4회이다.

그리고, 이렇게 방문하는 횟수는 나라 $A$에 연결되어 있는 도로의 개수와 동일하다는 점을 확인할 수 있다.

실제로 나라 $B, C, D$ 모두 연결된 간선 개수(1개) 만큼만 방문한다는 사실을 알 수 있다.

주의할 점은 시작 나라 $S$인데, 시작 나라 $S$는 초기에 방문하는 비용도 계산해야 하므로 연결된 간선 횟수보다 한 번 더 방문해야 한다는 것이다.

... 사실 말은 길게 했지만, 쓰고 보니 그냥 트리에서의 DFS를 돌리는 것을 생각하면 쉬울 것 같다.

나라가 $N$개이고 도로가 $N-1$개이므로, 이러한 그래프는 시작 나라를 루트 노드로 둔 트리라고 생각해도 좋다. (사이클이 존재하지 않으므로)

그리고 루트 노드에서부터 모든 노드를 순회한 뒤에 다시 루트 노드로 돌아오기 위해선, 반드시 DFS로 가장 깊이 있는 노드까지 들어간 뒤에 빠져나오며 순회하는 방법밖에는 없다.

이 경우, 당연히 모든 간선들을 2회 방문하고, 루트 노드를 제외하면 모든 노드는 연결된 간선의 수만큼 방문해야 하는 것이다.

따라서, 이 과정을 통해 우리는 다음과 같은 사실을 도출해 냈다.

"이미 그래프가 만들어진 경우, 해당 그래프에서 시작 나라에서 시작하여 모든 나라를 순회하고 시작 나라로 돌아오는 데 필요한 비용은 (모든 도로의 비용 * 2) + (각 나라의 비용 * 나라와 연결된 도로 개수) + (시작 나라의 비용) 으로 나타낼 수 있다!"

그럼 이를 토대로, 다음과 같은 사실도 깨달을 수 있다.

"어차피 시작 나라는 총 비용에서 (시작 나라의 비용) 만큼만을 차지하므로, 시작 나라는 단순히 비용이 최소인 나라를 아무렇게나 잡아도 된다!"

그런데 그럼 어떻게 $P$개의 도로에서 $N-1$개의 도로만을 남기면서 저렇게 그래프를 형성할 수 있을까?

위에서 필요한 비용식인,

(모든 도로의 비용 * 2) + (각 나라의 비용 * 나라와 연결된 도로 개수) + (시작 나라의 비용)

을 다시 생각해 보자.

(시작 나라의 비용) 부분은 어차피 그래프를 어떻게 잡는지와 관계 없이 (방문 비용이 최소인 나라의 비용)으로 두면 된다는 사실을 깨달았으니, 이는 그래프 연결과는 연관이 없는 부분이므로 무시하자.

또한, (모든 도로의 비용 * 2) + (각 나라의 비용 * 나라와 연결된 도로 개수)를 도로 연결 관점에서 보자면, 도로 하나를 연결할 때 드는 비용은 (해당 도로의 이동비용 * 2) + (해당 도로가 연결하는 각 나라의 비용의 합) 으로 나타낼 수 있다.

따라서, 그래프를 형성할 때는 (도로의 이동비용 * 2) + (해당 도로가 연결하는 각 나라의 비용의 합) 을 최소화 하는 방식으로 $N-1$개의 도로를 고르기만 하면 된다!

이는 간선 하나의 비용이 (해당 간선의 비용 * 2) + (해당 간선이 연결하는 각 정점의 비용의 합)인 최소 스패닝 트리를 만드는 것과 완벽하게 동일하므로, 풀이는 단순히 위의 식대로 간선의 비용을 설정해준 뒤 최소 스패닝 트리를 만들어 준 다음, 비용을 계산해 주면 된다.

5. 코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main() {
    int n, p;
    int a, b, c;
    int cost[10005];
    int minn, st;
    int ans = 0;
    vector<int> vst;
    vector<vector<pair<int, int>>> edge;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    cin >> n >> p;
    edge = vector<vector<pair<int, int>>>(p+1);
    vst = vector<int>(n+1, 0);

    minn = INT_MAX;
    st = -1;
    for (int i=1; i<=n; i++) {
        cin >> cost[i];
        if (minn > cost[i]) {
            st = i;
            minn = cost[i];
        }
    }
    ans += minn;

    for (int i=0; i<p; i++) {
        cin >> a >> b >> c;
        edge[a].push_back({cost[a]+cost[b]+2*c, b});
        edge[b].push_back({cost[a]+cost[b]+2*c, a});
    }

    for (int i=0; i<edge[st].size(); i++) {
        pq.push({edge[st][i].first, edge[st][i].second});
    }
    vst[st] = 1;

    while (!pq.empty()) {
        int node, dist;
        node = pq.top().second;
        dist = pq.top().first;
        pq.pop();

        if (vst[node])  continue;
        vst[node] = 1;
        ans += dist;

        for (int i=0; i<edge[node].size(); i++) {
            if (vst[edge[node][i].second]) continue;
            pq.push({edge[node][i].first, edge[node][i].second});
        }
    }

    cout << ans;

}

6. 여담

문제 작성하다가 본 건데, 문제 처음에는 나라라고 하다가 중간엔 갑자기 "모든 도시를 한 번 이상 방문한다"고 한다...?

사실 필자도 풀이 작성하면서 자꾸 나라를 도시라고 잘못 써서 지웠다 다시 쓰는 경우가 수도 없이 많았다...

https://acmicpc.net/problem/3031

* 혹시라도 맞왜틀??? 을 외치며 블로그에 들어오신 분이라면 "여담" 부분에 몇 가지 예외 케이스를 작성했으니 확인해 보시기 바랍니다.

1. 문제

- $N$개의 팀의 경기 수 / 이긴 횟수 / 비긴 횟수 / 진 횟수 / 승점이 주어진다. 이 때, ?로 주어지면 해당 부분은 알려지지 않았다는 의미이다.

- 승리 시에 팀은 3점, 비긴 시에 팀은 1점의 승점을 획득한다.

- 각 팀의 ?로 되어 있는 부분이 무엇인지 유추하여라.

- 각 팀의 최대 경기 수는 100회이며, 빈 칸을 채우는 경우가 유일한 경우만 주어지는 것이 보장된다.

2. 힌트

힌트 1

힌트 2

힌트 3

3. 문제 관찰 과정 및 풀이

처음 이 문제를 보자마자 든 생각은 "개쉬운데?" 였다.

사실 그도 그럴것이, 처음에는 케이스가 그렇게 많이 나뉠줄 몰랐기 때문이다.

사실 이 문제는 케이스를 잘 나눠서 어떻게든 ?를 채우기만 하면 되기 때문에, 문제 관찰 과정이랄게 딱히 없으니 케이스를 나누며 문제를 풀어 보자.

우선, 기본 조건을 먼저 생각해 보자.

"각 팀은 최대 100경기를 소화했다" 라는 것은, 승 / 무 / 패 의 합이 최대 100이라는 뜻이다.

따라서, 문제를 풀기 이전에 먼저 승 / 무 / 패 중 하나 혹은 두개의 합이 100이라면, 다른 승 / 무 / 패 중 주어지지 않은 것이 있더라도 0으로 바꿔줄 수 있다.

또한, 총 경기 수가 이미 주어진 경우에 한해서, 위와 동일하게 승 / 무 / 패 중 하나 혹은 두개의 합이 총 경기 수와 동일하다면, 다른 승 / 무 / 패 중 주어지지 않은 것이 있더라도 0으로 바꿔줄 수 있다.

(TMI - 원래 풀이 과정에서는 가장 늦게 생각나버려서 시간 소진을 많이 하게 된 부분이지만, 풀이 과정 설명을 위해선 위쪽에 서술해야 하므로 어쩔 수 없이 여기에 작성하였다.)

이제 케이스를 나눠 보자.

케이스를 어떻게 나눠야 할지는 사람마다 생각이 다를 수 있겠지만, 나는 총 경기 수와 승점 두 부분의 케이스를 먼저 나눠 주었다.

- 총 경기 수와 승점 둘 모두 주어지지 않은 경우

이 경우, 승/무/패 모두 알려져 있어야 한다. 셋 중 하나라도 모르는 경우에는 승점과 경기 수 모두 구할 수 없기 때문이다.

- 총 경기 수가 알려져 있지 않지만 승점이 알려져 있는 경우

이 경우 주의해야 하는 점은 총 승점에 의해 승/무/패 횟수가 고정되는 경우가 있을 수 있다는 것이다.

가령, 총 승점이 298점인 경우를 상정해 보자.

최대 경기 횟수가 100회이기 때문에, 이 경우는 100 99 1 0 298 만으로 주어질 수 있다.

따라서, 총 경기 횟수 / 승 / 무 / 패 모두 알려져 있지 않고 총 승점만 알려져 있는 경우에도 정답이 도출될 수 있다.

이 점에 유의하여 승점에 따라 승 / 무 / 패 횟수를 선택하면 된다.

이 때, 반드시 방법이 유일한 경우만 제시된다고 하였으므로 이미 주어진 것이 무엇인지만 잘 고려하면서 대충 때려박으면 된다.

- 총 경기 수가 알려져 있지만 승점이 알려져 있지 않은 경우

승점이 알려져 있지 않다는 것은, 승 / 무 / 패의 횟수가 총 경기 수에 의해서만 결정되므로 셋 중 두개 이상은 반드시 알려져 있다.

따라서 그냥 하나씩 확인해보면서 승 / 무 / 패 횟수를 정하고, 총 승점도 그에 따라 결정해 주면 된다.

- 총 경기 수와 승점이 모두 알려져 있는 경우

총 경기 수와 승점이 모두 알려져 있다면, 승 / 무 / 패 횟수를 간단히 구할 수 있다.

이미 무승부 횟수가 정해져 있다면 승리 횟수를, 이미 승리 횟수가 정해져 있다면 무승부 횟수를 쉽게 구할 수 있다.

만약 무승부 / 승리 횟수 모두 정해져 있지 않았다면 패배 횟수가 주어졌는지 여부로 판단해야 한다.

패배 횟수가 정해져 있다면 승점과 경기 수에 의하여 승 / 패 횟수가 정해질 수 있기 때문이다.

가령 7 ? ? 1 6으로 정보가 주어진다면, 승리 1회 / 무승부 3회 또는 승리 2회 / 무승부 0회는 불가능하며 오직 승리 0회 / 무승부 6회만 가능하기 때문이다.

그러나 패배 횟수가 정해져 있지 않다면 빈칸을 채우는 방법이 유일한 경우만 주어진다는 제한 조건에 의하여 그런 제한 조건을 생각하지 않고 단순히 승 횟수를 승점 / 3, 무승부 횟수를 승점 - (승리 횟수 * 3)으로 구할 수 있다.

이 때의 패배 횟수는 총 경기 수 - 승리 횟수 - 무승부 횟수 로 구할 수 있을 것이다

모든 케이스를 나눴으므로, 이제 이를 직접 구현해 보자.

4. 코드

(코드가 많이 더럽다... ㅠㅠ)

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main() {
    int n;
    int games, win, lose, draw, points;
    string a, b, c, d, e;
    cin >> n;
    for (int i=0; i<n; i++) {
        games = win = lose = draw = points = -1;
        cin >> a >> b >> c >> d >> e;
        if (a!="?") games = stoi(a);
        if (b!="?") win = stoi(b);
        if (c!="?") draw = stoi(c);
        if (d!="?") lose = stoi(d);
        if (e!="?") points = stoi(e);

        // 100경기 제한에 의한 win, draw, lose 결정
        if (win == 100) draw = lose = 0;
        if (draw == 100)    win = lose = 0;
        if (lose == 100)    win = draw = 0;
        if (win+draw == 100)    lose = 0;
        if (draw+lose == 100)   win = 0;
        if (win+lose == 100)    draw = 0;

        if (games == 0) win = draw = lose = points = 0;

        if (games == -1) {
            // game을 모를 때
            if (points == -1) {
                // game과 points 모두 모를 때
                points = 3*win + draw;
            }
            else {
                // game은 모르고 points를 알 때
                if (lose == -1) lose = 0;
                if (win == -1 && draw == -1) {
                    // win, draw 모두 알려지지 않았으면 반드시 이렇게 되야 함.
                    win = points / 3;
                    draw = points - (3*win);
                }
                if (win == -1)  win = (points - draw)/3;
                if (draw == -1) draw = points - (3*win);
            }

            games = win + lose + draw;
        }
        else {
            if (win == games) draw = lose = 0;
            if (draw == games)    win = lose = 0;
            if (lose == games)    win = draw = 0;
            if (win+draw == games)    lose = 0;
            if (draw+lose == games)   win = 0;
            if (win+lose == games)    draw = 0;
        }

        if (points == -1) {
            // games는 있고 points는 없는 경우
            if (win == -1)  win = games - draw - lose;
            if (lose == -1) lose = games - win - draw;
            if (draw == -1) draw = games - win - lose;
            points = 3*win + draw;
        }

        // games, points 모두 값이 있을 때
        if (win == -1)  {
            if (draw == -1) win = points / 3;
            else    win = (points - draw) / 3;
        }
        if (draw == -1) draw = points - (3 * win);
        if (lose==-1)   lose = games - win - draw;
        while (win + draw < games - lose) {
            win--;
            draw+=3;
        }
        cout << games << " " << win << " " << draw << " " << lose << " " << points << "\n";
    }
}

5. 여담

정말 정말 쉬워 보이는 문제이지만, 고려해야 하는 부분들이 너무 많아서 그냥 화가 계속 난다.

만약 대회에서 이런 문제가 나왔다?? 진짜 이 문제 하나때문에 대회 망하는 팀이 한둘이 아닐 거라는 생각이 든다..

혹시라도 "맞왜틀??????" 을 외치며 이 블로그에 들어온 사람이 있다면 내가 문제를 풀면서 넣어 봤던 여러 케이스들을 작성해 본다.

정말 풀면서 고통스러웠던 문제... 

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

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

앞으로 쓸 백준 문제의 힌트와 관찰 과정, 풀이를 쓰는 과정에서 어떤 생각으로 어떻게 작성할 것인지 기본적인 템플릿을 작성합니다.

백준 문제풀이 글의 목표는 다음과 같습니다.

1. 문제 풀이 과정 기록: 제가 문제를 풀 때 어떤 방식으로, 어떻게 생각하면서 해답에 도달했는지 기록합니다.

문제의 핵심 아이디어에 도달하는 데 어떤 과정을 거쳤는지, 어떤 포인트를 중점으로 보며 문제를 해결했는지 기록하며 비슷한 문제가 나왔을 때 더 쉽게 풀 수 있도록 합니다.

2. 알고리즘 학습자 및 문제 풀이자에게 힌트 제공: 문제를 풀다 보면 직접적인 정답이 아니라 약간의 힌트가 필요할 때가 있을 수 있습니다.

문제 풀이 시에 초기 접근 방식부터 핵심적인 아이디어를 찾는 과정까지, 미약하게나마 문제의 힌트를 제공하여 아예 처음부터 답안을 보기보다는 조금 더 본인 스스로 풀 수 있는 능력을 발전시킬 수 있게 합니다.

3. 문제 풀이 과정 공유: 단순 풀이뿐만 아니라 풀이 시에 어떤 접근 방식을 거쳤는지, 핵심적인 아이디어를 얻기 위해 관찰했던 과정은 무엇인지, 풀이 시에 유의할 점은 어떤 점들이 있을지 등 풀이 과정에서 있는 생각 절차들을 모두 작성합니다.

"대체 저런 생각은 어떻게 하는 걸까?"가 아닌, "저래서 저런 생각이 나왔구나" 싶은 정도까지 최대한 세세하게 풀이로 가는 길을 작성하고자 합니다.

물론 일부 문제들은 반짝이는 아이디어가 필요한 경우가 있겠지만, 그런 경우에도 어떤 관찰들을 통해 인사이트를 얻을 수 있었는지까지 작성합니다.

쓰는 글들의 대상 독자는 다음과 같습니다.

1. 골드 하위권~플레 하위권 수준의 문제를 풀고자 하는 사람들: 제가 이정도 실력이라.. ㅎㅎ

2. 풀이를 생각하다가 접근 방식부터 막힌다거나, 핵심적인 아이디어를 도저히 찾을 수 없는 사람들: 힌트만 보고 빠질 수 있도록 했습니다.

3. 문제 풀이뿐만 아니라 풀이 과정 및 증명 과정이 궁금한 사람들: 전 (대회가 아닌 이상) 웬만하면 전부 다 증명하면서 풀이를 전개하기 때문에, 대부분의 풀이 과정 및 증명을 찾을 수 있을 것 같습니다.

다만, 풀이 과정에 중점적으로 맞춰진 포스팅들이기에, 코드 자체에 대한 고찰은 많이 없을 것 같습니다.

가령, 세그먼트 트리를 사용하는 문제에서 세그먼트 트리의 구현을 어떻게 해야 하는지 등에 대한 내용은 따로 작성하지 않습니다.

또한, 특정 알고리즘을 단순히 구현하는 문제나 너무 웰-노운인 문제들은 따로 풀이를 작성하지 않습니다.

아래부터는 풀이 포스팅의 템플릿입니다.

어떤 부분들이 내용에 들어가고, 어떤 생각들을 중점으로 글을 작성하는지를 나타냅니다.

[템플릿]

https://acmicpc.net/problem/{문제 번호}

- 문제 링크를 답니다.

1. 문제

- 문제를 간략히 추상화하여 작성합니다.

- 문제를 풀기 위해 필요한 최소한의 조건들만 나열합니다.

- 문제를 너무 추상화하거나 조건을 풀어서 설명하여 문제 파트를 읽기만 해도 힌트가 되는 경우는 발생하지 않도록 주의합니다.

2. 힌트

- 문제 풀이에 필요한 힌트가 들어가는 곳입니다.

- 총 세 가지 힌트가 주어지며, 각 힌트는 접은 글 안으로 넣습니다.

- 힌트 1부터 힌트 3까지, 점점 더 자세한 힌트를 작성합니다.

- 구현 방식에 대한 내용은 그 자체가 중요한 아이디어가 아닌 이상 힌트로 기술하지 않습니다.

- 각 힌트에서 주로 어떤 내용이 들어가는지 접힌 글 안에 작성합니다.

힌트 1

힌트 2

힌트 3

3. 문제 관찰 과정 및 풀이

3-1. 문제 관찰 과정

- 문제 관찰 과정을 상세하게 기록합니다.

- 필자가 문제를 풀면서 처음에 가졌던 생각부터, 어떤 순서대로 관찰을 했는지 작성합니다.

- 주로 예제 입력을 토대로 관찰하는 방식을 서술하거나, 어떻게 특정 관찰을 시도하게 되었는지까지 상세하게 기록합니다.

- 간단한 예시부터 생각하기, 순서를 바꿔서 생각하기, 순서를 정해서 생각하기 등, 문제를 풀 때 의식하고 사용할 수 있는 문제 풀이 기법도 서술합니다.

3-2. 문제 풀이

- 직접적인 풀이를 제시합니다.

- 문제 관찰이 모두 끝난 후에, 어떤 테크닉이나 어떤 구현 방식을 사용하여 구현해야 하는지를 기술합니다.

- 풀이 방식과, 그렇게 풀이해도 되는 이유를 증명하거나 납득할 수 있도록 설명합니다.

- 보통은 문제 관찰 과정과 문제 풀이가 한 단락 안에 함께 들어있지만, 풀이가 길어지거나 관찰과 구현이 거의 유사한 수준으로 구현의 비율이 높은 경우에는 나눠질 수 있습니다.

- 구현 시에 주의해야 할 점들이나, 실수하기 쉬운 점들도 제시합니다. (문제 제한 조건에 따른 자료형 선택 등)

4. 코드

- 해답 코드를 작성합니다.

- 보통 따로 주석을 작성하지는 않으나, 풀이 시에 필자가 작성한 주석의 경우 들어있을 수 있습니다.

// 코드는 이렇게 코드블럭에 삽입됩니다.
// 코드에 대한 자세한 설명은 일반적으로 생략합니다.
// 코드가 너무 길어지거나 필자가 보기에도 너무 더러워 보인다면, 간략하게 의사 코드로 작성할 수 있습니다.
// 보통 의사 코드는 <코드> 부분이 아니라, <풀이> 부분에 있을 예정입니다.

5. 여담

- 풀이 중에 필자가 실수한 점들이나, 풀이 중에 생각했던 잘못된 풀이 등 실제 풀이 과정에는 큰 영향이 가지 않는 소소한 내용들을 작성합니다.

- 다른 풀이가 있다거나, 정해가 아니지만 그래도 풀리기는 하는 방식을 이곳에 서술합니다.

- 문제 풀이 꼼수도 이곳에 작성합니다. (예: "그냥 1번부터 10번까지 규칙을 대강 나열하면 ~~수열과 비슷해 보이므로, 이를 구현하여 대충 제출해도 Proof By AC로 맞았습니다!!를 받을 수는 있습니다." 와 같은...)

- 그냥 심심해서 써놓은 잡담들도 여기에 들어갑니다.

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인 것 같은데, 나중에 그 풀이도 살펴봐야겠다.