[백준][C++] 2473번: 세 용액 <208>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

 

2473번: 세 용액

생각의 흐름

용액 3개를 선택할 때 하나는 고정값으로 두는것이 핵심이다.

 

예를 들어 다음과 같은 input이 있다.

7
-2 -3 -24 -6 98 100 61

처음 용액의 목록을 input으로 받은 후, 오름차순으로 정렬하면 다음과 같아진다.

-24 -6 -3 -2 61 98 100

여기서 첫 반복때 -24 를 고정값으로 둔다. 이 용액은 무조건 선택한다 생각하면 된다.

 

나머지 -6 부터 100 중에 2개를 선택하면서 범위를 좁혀가면 된다.

1) -24 는 고정이고, -6 과 100을 선택하게 된다. => 합은 70 => 0보다 크니 right를 -1 시킨다.

2) -24 는 고정이고, -6 과 98을 선택하게 된다. => 합은 68 => 0보다 크니 right를 -1 시킨다.

3) -24 는 고정이고, -6 과 61을 선택하게 된다. => 합은 31 => 0보다 크니 right를 -1 시킨다.

3) -24 는 고정이고, -6 과 -2을 선택하게 된다. => 합은 -32 => 0보다 작으니 left를 +1 시킨다.

3) -24 는 고정이고, -3 과 -2을 선택하게 된다. => 합은 -5 => 0보다 작으니 left를 +1 시킨다. => left 와 right 값이 같아지니 종료

 

다음으로는 -6을 고정값으로 두고, -3 부터 100 까지 반복하면 된다.

이런식으로 반복하면서 답을 갱신해 나가면 된다.

 

나의 코드

#include <bits/stdc++.h>
using namespace std;
#define MAX 1001

int N;
long long vec[5000];
long long arr[3];

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

    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> vec[i];
    }
    sort(vec, vec + N);

    long long ans = LONG_LONG_MAX;
    for(int i = 0; i < N-2; i++) {
        int third = vec[i];
        int left = i+1;
        int right = N-1;
        while (left < right) {
            long long temp = third + vec[left] + vec[right];
            if(ans > llabs(temp)){
                ans = llabs(temp);
                arr[0] = third;
                arr[1] = vec[left];
                arr[2] = vec[right];
            }
            if (temp < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    cout << arr[0] << " " << arr[1] << " " << arr[2];

    return 0;
}