cdjs의 코딩 공부방

G5 | 14699 - 관악산 등반

걸린 시간: 약 15분 (부정확)

체감 난이도: G5 ~ G4 사이 그 어딘가 애매한 지점

시도 횟수: 1회

풀이 쓸 의향: 下

풀이:

여담: 친구가 암만봐도 골드 5 아닌것같다고 해서 풀어본 문제.

솔직히 아이디어 자체는 G5가 맞는데 그래프기도 하고 이런저런 구현방법 잘 모르면 시간 끌릴수도 있겠다 싶어서 G4로 난이도 기여함.

P5 | 2463 - 비용

걸린 시간: 45분

체감 난이도: P4 하위권

시도 횟수: 2회

풀이 쓸 의향: 中

풀이:

여담: disjoint set 구현할 때 두 root값(그래프 크기값)을 곱하는 부분이 있었는데, root값을 int로 둬서 한번 틀림.

솔직히 처음 봤을때 바로 MST(Maximum)이 떠올랐는데, 실상 풀이는 MST를 안쓰는게 더 편해서 오히려 생각이 더 꼬였던 것 같다.

(풀이 메모)

P4 | 1280 - 나무 심기

걸린 시간: 약 40분 (부정확)

체감 난이도: P5 상위권

시도 횟수: 3회

풀이 쓸 의향: 下

풀이

여담: 

나머지 연산 실수때문에 한 번, 값 범위가 0부터 시작인거 못봐서 한 번 틀렸다.

P5 | 14572 - 스터디 그룹

걸린 시간: 약 30분

체감 난이도: P5 하위권

시도 횟수: 1회

풀이 쓸 의향: 下

풀이

여담: vector<pair<int, vector<int>>>라는 괴상한 자료구조를 만들어서 풀었다.

실력 차이가 D 이하인 모든 구간에서 최대한 많은 사람을 넣도록 투포인터로 풀린다는 아이디어가 쉬운 사람한테는 너무 쉽고, 어려운 사람한테는 너무 어렵게 보일만 한듯.

P3 | 10542 - 마피아 게임

걸린 시간: 1시간 10분

체감 난이도: P3

시도 횟수: 8회

풀이 쓸 의향: 上

풀이

여담: 정말 재밌게 푼 문제.

중간에 많이 해메서 좀 코드가 많이 더럽다. 남은 cycle 처리를 이상하게 해서 자꾸 틀리다 결국 발견해서 풀었다.

(풀이 메모)

사실 입대 이후 거의 매일 문제를 한두문제씩은 풀고 있는데, [백준 문제 풀이] 탭에 글을 올릴 때는 꽤나 오랜 시간이 걸리기 때문에 2시간 남짓의 연등 시간동안 문제를 풀고 힌트와 풀이까지 작성하기에는 상당히 힘에 부쳤다.

사실 그래서 "와 이 문제 괜찮네... 블로그에 올려야겠다" 생각했던 문제들도 올리지 못하다가 풀이를 까먹어서 못올린 문제가 꽤 된다.

문제를 풀면서 배웠던 점들, 익혔던 점들을 기록하고 추후 풀이글 작성에 도움이 되고자 매일매일 풀었던 문제를 기록하고, 풀이 및 간단한 생각을 기록하고자 한다.

사실 필자가 문제를 풀 때는 항상 메모장을 켜서 나 스스로의 대화를 하며 문제를 풀어나가는데, 아마 해당 메모장을 그대로 올린 뒤에 풀이를 대충 기록하는 방식으로 진행할 것 같다.

"나 스스로의 대화"가 뭔지는 다음 글을 보면 뭔 소리인지는 대충 알 수 있겠지만, 필자는 문제를 풀 때 생각났던 풀이들과 생각들을 모두 메모장에 기록하면서 문제를 푼다.

그 생각이 틀린것 같아도 나중에 지우지는 않는데, 틀린 생각인줄 알았다가 나중에 다시 생각해보니 방향성은 맞았던 경우가 한둘이 아니라 너무 멀리 딴 길로 새주는 것을 막아주는, 일종의 방파제 역할을 해 주기 때문이다.

따라서 해당 기록을 보다 보면 내가 어떤 생각으로 문제를 풀었는지가 적나라하게 드러나고, 그만큼 더 복기하기 쉬워서 상당히 괜찮은 습관이라고 스스로 생각하고 있다.

다만 문제를 풀다가 미쳐버려서 욕지거리를 쓰기도 하는데... 그것도 내가 얼마나 고민했는지 알려주는 일종의 표시가 되니까 그냥 남겨 둘 생각이다.

문제 풀이 기록장에는 딱히 템플릿은 없을 것 같은데, 그냥 간단하게 문제 번호 / 링크 / 풀게 된 계기 (랜덤디펜스, 특정 알고리즘 학습 등) 따위를 적은 뒤에 걸린 시간, 시도 횟수, 메모장 내용 복붙 및 여담 작성으로 이루어질 것 같다.

백준 문제만 아니라 가끔 코드포스 문제나 기타 대회 문제들을 올리기도 할 것 같다.

1일 1글 작성... 어쩌면 가능할지도??!

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$을 메모이제이션 하는 방식을 사용했지만, 분할 정복을 활용하여 제곱을 계산해도 시간 안에 풀 수 있다.