[Algorithm]Baekjoon 20366번 :: 같이 눈사람 만들래?

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
 
using namespace std;
 
struct Node
{
    int index1;
    int index2;
    int size;
};
 
bool cmp(const Node& a, const Node& b)
{
    return a.size < b.size;
}
 
int n;
int heights[601] = { 0 };
vector<Node> nodes;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> heights[i];
    }
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = i + 1; j < n; ++j)
        {
            nodes.push_back({ i,j,heights[i] + heights[j] });
        }
    }
 
    sort(nodes.begin(), nodes.end(), cmp);
 
    int answer = 0x3f3f3f3f;
 
    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;
}
 
 

 

당연히 600C4 하면 시간초과다.

그러니 어떻게든 조금만 더 줄여보자.

 

일단 만들 수 있는 눈사람의 경우의 수를 모두 구해보자.

그러면 600C2로 눈사람조합개수를 모두 구할 수 있다. (인덱스를 저장해야한다!)

그리고 정렬을 한번 해주자. 눈사람 조합 인덱스를 알고있으니, 그걸기반으로 눈사람크기를 구해서 오름차순 정렬을 해준다.

 

그러면! 이 정렬된 컨테이너 안에선 바로 자신의 오른쪽 인덱스가 자기와 가장 크기차이가 나지않는 눈사람조합이 된다.

(눈사람크기순으로 정렬했으니까)

 

다만, 바로 오른쪽 눈사람에 조합된 인덱스가 자기의 구성눈덩이 인덱스랑 겹치면 안된다. 왜냐하면 문제에서는 '서로 다른 눈덩이 4개'라고 했기 때문이다.

 

그러니 서로 4개가 전부 서로다른 눈덩이일경우 답을 갱신해주면 된다.