[Alogorithm] 백준 20366 같이 눈사람 만들래? - C++

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

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int n;
vector<int> snows;
vector<pair<int, pair<int, int>>> snowmans;

bool Same(const pair<int, int>& a, const pair<int, int>& b){
    if((a.first != b.first) && (a.first != b.second) && (a.second != b.first) && (a.second != b.second))
        return false;
    return true;
}

int main(){
    // init
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // input
    cin >> n;
    snows.resize(n);
    for(int i = 0; i < n; i++){
        cin >> snows[i];
    }

    // make all snowmans
    for(int i = 0; i < n-1; i++){
        for(int j = i + 1; j < n; j++){
            snowmans.push_back({snows[i] + snows[j], {i, j}});
        }
    }

    // solution
    int answer = static_cast<int>(10e9);
    sort(snowmans.begin(), snowmans.end());
    for(int i = 0; i < snowmans.size()-1; i++){
        for(int j = i+1; j < snowmans.size(); j++){
            if(Same(snowmans[i].second, snowmans[j].second))    continue;

            answer = min(answer, snowmans[j].first - snowmans[i].first);
            break;
        }
    }

    cout << answer << '\n';
}

---

 두 포인터로 분류되었던 문제인데 제 코드가 그게 맞는지는 모르겠습니다. 눈사람을 만들 수 있는 모든 조합을 배열에 넣어둔 뒤 이후 그 배열을 전부 돌아보면서 탐색하는 것입니다.

 

 처음에 시간 초과가 났는데 잘 살펴보니 안쪽 for문에서 answer 갱신이 이루어지면 그 후는 무조건 차이가 더 크기 때문에(정렬이 되어 있어서) break를 통해 성능 향상을 해줘야 합니다.