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

문제 링크

BOJ_20366: 같이 눈사람 만들래?

문제

N개의 숫자 중 서로다른 4개를 선택한다.
4개 중 2개씩 더한 합의 차가 최소가 되는 경우를 구하는 문제이다.

풀이

N은 최대 600이다. 반복문을 4번 돌려 4개의 수를 선택하면 편하겠지만 600600600*600 = 시간초과이다. 따라서 조금 더 효율적으로 합이 최소가 되는 경우를 구해야한다.

수들이 정렬돼있다고 가정했을 때 4가지 임의의 수 a, b, c, d를 뽑았다고 생각해본다.
이 경우 합의 차가 최소가 되는 경우는 정해져있다.
가장 작은 수 a + 가장 큰 수 d - (b+c) 이다.
즉 끝의 수 2개를 결정하면, 나머지 수는 결정된 수 사이에 존재한다.

반복문을 이용해 a,d를 결정한다. -> O(N^2)
그리고 나머지 수 두개 (b,c)를 결정하는 과정에서 투포인터를 활용해 시간복잡도를 최적화한다.
a+d와 b+c를 각각 sumA, sumB로 설정한다.
만약 sumB<sumA라면 sumB의 크기를 키워야한다. 수들이 정렬돼있고 b와 c가 a,d 사이 구간의 양 끝에서 시작한다면 b+c의 값이 커지기 위해서는 b의 값을 증가시켜야한다.
이렇게 하면 O(N)에 b와c를 결정할 수 있다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>

#define endl "\n"

using namespace std;

int N;
int arr[606];

void Solve() {
    cin>>N;
    int left, right, sumA, sumB, result, answer = INT_MAX;
    for(int i=0; i<N; i++){
        cin>>arr[i];
    }

    sort(arr, arr+N);

    for(int i=0; i<N-2; i++){
        for(int j= i+3; j<N; j++){
            
            left = i+1; right = j-1;
            sumA = arr[i] + arr[j];
            while(left<right){
                sumB = arr[left]+arr[right];
                result = abs(sumA-sumB);
                answer = min(answer, result);
                
                if(answer == 0) {cout<<answer; return;}
                
                if(sumA>sumB) left++;
                else right--;
            }
        }
    }

    cout<<answer;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    Solve();

    return 0;
}