[백준] 20366번 : 같이 눈사람 만들래? (C++)

20366번 : 같이 눈사람 만들래?

---

문제)

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

 

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

 

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

 

 

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

 

 

 

입력 :

첫째 줄에 N (4 ≤ N ≤ 600)이 주어진다.

둘째 줄에는 각 눈덩이 i (1 ≤ i ≤ N)의 지름을 의미하는 정수 Hi (1 ≤ Hi ≤ 109)가 공백으로 구분되어 주어진다.

 

 

 

출력 :

만들 수 있는 두 눈사람의 키 차이 중 최솟값을 나타내는 정수를 출력하라.

 

 

 

 

 

 

 

풀이)

 

// 20366. 같이 눈사람 만들래?
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
 
using namespace std;
 
vector<long long> vec;
 
int main()
{
    int n;
    cin >> n;
    vec.resize(n);
    for (long long& ele : vec) cin >> ele;
    sort(vec.begin(), vec.end());
 
 
    long long ans = LLONG_MAX;
 
    // 엘사의 눈사람을 먼저 만들어준다.
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            long long elsa = vec[i] + vec[j];
 
            // 엘사의 눈사람이 만들어진 후,
            // 투 포인터를 이용해 안나의 눈사람도 만들어준다.
            int s = 0;
            int e = n - 1;
 
            while (s < e)
            {
                if (s == i || s == j)
                {
                    s++;
                    continue;
                }
 
                if (e == i || e == j)
                {
                    e--;
                    continue;
                }
 
                long long anna = vec[s] + vec[e];
                ans = min(ans, abs(elsa - anna));
 
                long long diff = elsa - anna;
                
                if (elsa >= anna) s++;
                else if (elsa < anna) e--;
            }
        }
    }
 
    cout << ans;
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/20366 

20366번: 같이 눈사람 만들래?