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

문제 링크: www.acmicpc.net/problem/20366

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

1. 주의할 점

- 4개의 수를 어떤 방식으로 뽑을 것인지 잘 생각한다

- 정렬 이후, 인접합 4개를 조작하여 답을 구할 경우, 반례가 존재한다.

반례)
6
1 2 1000 2000 10001 10002
답: 0

 

2. 구현

- 조합을 통해 2개 공의 합이 나타낼 수 있는 높이를 벡터에 저장한다. 이때, 벡터는 사용한 번호 2개, 2개의 합 총 변수가 3개인 구조체 형태로 이루어져있다.

- 벡터를 총합의 오름차순으로 정렬한다

- For문 2개를 수행하여 서로 다른 4개의 눈을 사용했다면 Result와 비교한다. 단, 오름차순으로 정렬되어있으므로 Result와 비교를 했다면 내부 For문은 그 이후로 탐색하지 않도록 한다(탐색해도 더 큰 차이를 나타내기 때문)

#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
struct info{
    int a, b;
    long long val;
};
bool cmp(info &a, info &b){
    return a.val < b.val;
};
info tmp;
int arr[601];

int main() {
    int num;
    cin>>num;
    for(int i=0;i<num;i++)
        cin>>arr[i];
    vector<info> v;
    for(int i=0;i<num-1;i++){
        for(int j=i+1;j<num;j++){
            long long add = arr[i]+arr[j];
            tmp.a=i;
            tmp.b=j;
            tmp.val = add;
            v.push_back(tmp);
        }
    }
    sort(v.begin(),v.end(),cmp);
    long long result=9876543210;
    
    for(int i=0;i<v.size()-1;i++){
        for(int j=i+1;j<v.size();j++){
            if(v[i].a!=v[j].a && v[i].a!=v[j].b && v[i].b!=v[j].a && v[i].b!=v[j].b){
                result = min(result,v[j].val-v[i].val);
                break;
            }
        }
    }
    cout<<result;
    return 0;
}

 

위의 풀이 말고 이분탐색으로도 풀이할 수 있을 것 같다. 하지만 방법이 떠오르지 않아 다른분들의 코드를 참조했다.

Hint: 4개의 눈 중에서 양끝을 고정시키고 안의 2개의 값들을 조작한다