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

문제

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

 

알고리즘

정렬

 

풀이

서로 다른 네 수를 뽑아 두 개씩 짝지었을 때, 차이를 최소화 하는 문제입니다.

 

NC2를 통해 가능한 조합을 뽑고 나서 인덱스들이 가리키는 수들의 합을 기준으로 정렬한 후 풀면 됩니다. 정렬된 배열(벡터)에서 각 수의 조합이 서로 다른 인덱스로 이루어졌는지 확인하면 됩니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

typedef tuple<int, int, int> tp;

int N, ans = INT_MAX;
vector<int> vt;
vector<tp> vt2;
int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> N;
    rep(i, N) {
        int x;
        cin >> x;
        vt.emplace_back(x);
    }
    for (int i = 0; i < vt.size() - 1; ++i) {
        for (int j = i + 1; j < vt.size(); ++j) {
            vt2.emplace_back(i, j, vt[i] + vt[j]);
        }
    }
    sort(vt2.begin(), vt2.end(), [](const tp& a, const tp& b) { return get<2>(a) < get<2>(b); });
    for (int i = 0; i < vt2.size() - 1; ++i) {
        for (int j = i + 1; j < vt2.size(); ++j) {
            auto [a, b, c] = vt2[i];
            auto [e, f, g] = vt2[j];
            if (a != e && a != f && b != e && b != f) {
                ans = min(ans, g - c);
                break;
            }
        }
    }
    cout << ans;
    return 0;
}