2473번 : 세 용액 [C++]

문제 링크

성공 여부(걸린 시간): 성공 (19분 25초)

아이디어

문제 자체는 간단하다. 세 용액의 합이 0에 제일 가까운 값을 만드는 세 용액을 구해 오름차순으로 출력하는 것이다.

그렇게 하기 위해서는 우선 이분탐색 또는 투포인터로 가능했는데 나는 투포인터를 사용해서 풀어주었다.

 

그렇게 하기 위해서는 우선 입력 받은 값들을 정렬해주고 첫번째 용액을 for문으로 선택 후 

나머지 두 배열을 현재 바로 다음 순서의 용액과 마지막 용액을 각각 left, right로 잡고 

 

sum이란 변수에 arr[i], arr[left], arr[right]의 합을 저장해주고 

sum의 값에 따른 분기를 통해서 다음 동작을 제어한다.

 

1. 만약 sum이 0이다?

-> 그럼 최소값을 이루는 조합 중에 하나임이 틀림없기에 바로 출력해주고 return해준다.

 

2. 만약 sum값의 절대값이 지금까지의 세 용액의 합의 절대값 중의 최소값 보다 작다?

-> 세 용액의 조합을 저장 + 최소값 최신화 해준다.

 

3. sum > 0이다?

-> 합을 더 줄일 필요가 있기에 right를 1 감소시켜준다.

 

4. sum < 0이다?

-> 합을 키울 필요가 있기에 left를 1 증가시켜준다.

 

그런데 약간의 우여곡절

처음에는 arr는 어차피 입력이 절대값 10이 최대이기 때문에 sum부분만 long값으로 해줬더니 틀렸다는 결과가 나와서 전부 long long으로 통일 시켜주었더니 통과했다. 그이유는 바로 ...

..

..

..

long = int + int + int 라고 했을때 

long에다가 int형인 값을 더하는 것이 아니라 = 하기 전까지 int로 계산이 되기때문에 오버플로우가 난 것이다.

풀이코드

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

typedef long long ll;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int N;
    cin >> N;

    vector<ll> arr(N, 0);
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }

    sort(arr.begin(), arr.end());
    vector<ll> answers(3, 0);
    ll answer = 0x7fffffffffffffff;
    for (int i = 0; i < N - 2; i++) {
        int left = i + 1;
        int right = N - 1;
        while (left < right) {
            ll sum = arr[i] + arr[left] + arr[right];
            if (sum == 0) {
                cout << arr[i] << " " << arr[left] << " " << arr[right];
                return 0;
            }
            if (abs(sum) < answer) {
                answer = abs(sum);
                answers = { arr[i], arr[left], arr[right] };
            }
            if (sum<0) {
                left++;
            }
            else {
                right--;
            }
        }
    }

    cout << answers[0] << " " << answers[1] << " " << answers[2];
    return 0;
}