백준 20366 - 같이 눈사람 만들래?

문제 설명

언니! 똑...똑똑...똑똑! 같이 눈사람 만들래~? ♪

언니 엘자와 동생 안나에게는 N개의 눈덩이가 있다. 각 눈덩이 i (1 ≤ i ≤ N)의 지름은 Hi 이다. 하나의 눈사람은 두 개의 눈덩이로 구성되며, 눈덩이 하나를 아래에 두고 그 눈덩이보다 크지 않은 다른 눈덩이를 쌓아올리는 방식으로 만들 수 있다. 이때, 눈사람의 키는 두 눈덩이 지름의 합과 같다.

엘자와 안나는 눈덩이 N개 중 서로 다른 4개를 골라서 눈사람을 각각 1개씩, 총 2개를 만들려고 한다. 두 자매는 두 눈사람의 키의 차이가 작을수록 두 눈사람의 사이가 좋을 것이라고 믿는다. 우리는 엘자와 안나가 가장 사이좋은 두 눈사람을 만들기 위해서 도와주려고 한다.

주어진 N개의 눈덩이를 이용하여 만들 수 있는 두 눈사람의 키 차이 중 최솟값을 구하는 프로그램을 작성하시오.

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 주어진 N개의 눈덩이 중 서로 다른 4개를 선택한 뒤 2개씩 짝지어 더한 결과의 차이가 가장 작게 만들어야 한다.

 

해당 문제는 투포인터로 해결할 수 있다.

얼핏 보면 포인터가 4개가 필요해 보인다.

엘사의 눈덩이 2개, 안나의 눈덩이 2개가 필요해 보이지만, 이를 컨트롤하기는 쉽지 않다.

5
3 5 2 5 9

위와 같은 입력이 주어졌을 때 정렬하면 다음과 같다.

2 3 5 5 9

 

이때, 엘사가 {2, 9}를 고르고 안나가{3, 5}를 골랐다고 가정해 보자.

그렇다면 차이는 $|(2+9) - (3+5)| = 3$이 된다.

이때, 안나의 눈사람이 더 작기 때문에 안나의 왼쪽(머리)을 키우거나 엘사의 오른쪽(몸통)을 줄여야 한다.

즉, 2번의 분기로 갈리게 된다.

이렇게 되면 $N*2^N$가 될 것이다. 

이를 해결하기 위해서는 하나를 고정하면 된다.

편의를 위해 엘사가 항상 큰 눈사람을 만든다고 할 수 있다.

따라서, 엘사의 눈사람의 크기는 2중 for문을 돌며 고정된 크기를 가진 상태에서 그 사이에 있는 눈덩이를 선택해 안나가 눈사람을 만든다고 생각하는 것이다.

for (int i = 0; i < N; i++)
{
    for (int j = 0; j < N; j++)
    {
        int left = i + 1;
        int right = j - 1;

        int e = getTall(i, j);
        while (left < right)
        {
            int a = getTall(left, right);
            ans = min(ans, abs(e - a));
            
            if (e < a) right--;
            else left++;
        }
    }
}

 

 

또 다른 풀이가 있다.

이는 다름 사람의 풀이를 참고하여 알아낸 것이다.

어차피 엘사의 눈사람의 크기를 고정하기 위해 2중 for문을 돌기 때문에 2개씩 눈덩이를 골라 만드는 조합을 만드는 것 역시 가능하다.

따라서, 2개씩 조합해 만들 수 있는 모든 눈사람의 경우의 수를 구한 뒤, 이를 크기순으로 정렬한다.

이후, 하나의 눈사람을 기준으로 그 눈사람보다 큰 눈사람들을 살펴보며 서로 다른 4개의 눈덩이를 쓴경우 크기의 차이를 갱신한다.

이렇게 처리하는게 시간이 훨씬 짧아 기록한다.

struct Node
{
    int index1;
    int index2;
    int size;
};

sort(nodes.begin(), nodes.end(), cmp);

int answer = INT_MAX;

for (int i = 0; i < nodes.size() - 1; ++i)
{
    for (int j = i + 1; j < nodes.size(); ++j)
    {
        if (nodes[i].index1 != nodes[j].index1 &&
            nodes[i].index1 != nodes[j].index2 &&
            nodes[i].index2 != nodes[j].index1 &&
            nodes[i].index2 != nodes[j].index2)
        {
            answer = min(answer, nodes[j].size - nodes[i].size);
            break;
        }
    }
}

cout << answer;

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int N;
int ans = INT_MAX;

vector<int> nums;

int getTall(int bottom, int top)
{
    return nums[bottom] + nums[top];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(4);  

    cin >> N;
    nums.resize(N);

    for (int i = 0; i < N; i++)
    {
        cin >> nums[i];
    }

    sort(nums.begin(), nums.end());

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            int left = i + 1;
            int right = j - 1;

            int e = getTall(i, j);
            while (left < right)
            {
                int a = getTall(left, right);

                ans = min(ans, abs(e - a));
                if (e < a)
                {
                    right--;
                }
                else
                {
                    left++;
                }
            }
        }
    }

    cout << ans;

    return 0;
}

---