[boj]20366 - 같이 눈사람 만들래? 풀이(투포인터, 정렬)

www.acmicpc.net/problem/20366

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

- 문제 유형 분류가 투포인터로 되어 있는데 눈사람을 만드는 모든 케이스를 만든 뒤 정렬하면서 중복되는지 여부만 체크해도 충분히 풀리는 문제였다. 투포인터로 된 스터디원 풀이도 봤는데 잘 이해가 가지 않았다.

- sort에 쓸 compare 함수를 짤 때 등호가 들어간 부등호를 쓰면 채점 시에 시간초과가 난다. 주의하자

- 구조체 생성자를 따로 작성 안해도 눈사람 배열에 {원소1, 원소2, 원소3} 을 push_back 하면 눈사람 구조체가 생성된다. 

- 엘자, 안나가 만들 수 있는 눈사람 케이스가 오름차순으로 정렬되어 있으므로 둘이서 만들 수 있는 눈사람 케이스인 경우 바로 break해서 정렬된 붙어있는 2개 원소끼리만 비교해나간다. 

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
#define INF 2109876543

struct El {
    int a, b, height;
    El(int _a, int _b, int _height) : a(_a), b(_b), height(_height){};
};

bool cmp(const El& e1, const El& e2) {
    return e1.height < e2.height;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i];
    }

    vector<El> elCase;
    for (int i = 0; i < n - 1; ++i) {
        for (int j = i + 1; j < n; ++j) {
            elCase.push_back(El(i, j, v[i] + v[j]));
        }
    }
    sort(elCase.begin(), elCase.end(), cmp);

    int diff = INF;
    for (int i = 0; i < elCase.size() - 1; ++i) {
        for (int j = i + 1; j < elCase.size(); ++j) {
            if (elCase[i].a == elCase[j].a || elCase[i].b == elCase[j].b || elCase[i].a == elCase[j].b || elCase[i].b == elCase[j].a)
                continue;

            diff = min(diff, elCase[j].height - elCase[i].height);
            break;
        }
    }

    cout << diff;
    return 0;
}