BOJ 2470 - 두 용액 (C++)

채원·2023년 11월 25일
0

이 문제는 사실 버전이 두 가지다.
두 용액
용액

둘이 뭔가가 다르긴 했는데 지금은 기억이 잘 안 난다.
근데 아무튼 중요한 건 사실상 같은 문제라 하나 풀고도 두 문제를 맞춘 것과 같은 효과를 낼 수 있다는 것(!)
그것도 심지어 골드 5(!!!)
완전히 남는 장사일 수 밖에 없다.

풀이 자체는 간단히 투 포인터를 이용해서 할 수 있다.
먼저 모든 원소를 소트한 뒤, 맨 왼쪽과 오른쪽에 포인터를 세팅해둔다. 그러면서 한 칸 한 칸씩 포인터를 옮기면서 두 포인터가 가리키고 있는 원소들의 합을 구하는 것이다. 만약 그 합이 0보다 크다면, 양수의 크기를 줄여야 하므로 오른쪽 포인터를 이동시키고, 반대라면 음수의 크기를 키워야 하므로 왼쪽 포인터를 이동시킨다. (이것이 가능한 것은 앞에서 원소를 소트해뒀기 때문이다. 만약 정렬되어 있지 않다면 이 방법을 사용할 수 없다.

이 과정을 반복하면서 합을 계산하고, 그 합이 만약 0과 가장 가까웠던 값보다 더 가깝다면 최소값을 갱신하고, 해당 원소를 저장한다. 이 과정을 두 포인터가 교차될 때까지 반복한다.


정답을 얻은 코드는 다음과 같다.

//두 용액 - 골드 5

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int a_l, a_r, min_char = 2*1e9;

void findMin(const vector<int>& arr) {
    int l = 0, r = arr.size() - 1;

    while (l < r) {
        int sum = arr[l] + arr[r];
        if (abs(min_char) > abs(sum)) {
            min_char = sum;
            a_l = arr[l];
            a_r = arr[r];
        }

        if (sum > 0) {
            r--;
        } else {
            l++;
        }
    }
}

int main() {
    int n;
    vector<int> arr;
    cin >> n;
    arr.assign(n, 0);

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    sort (arr.begin(), arr.end());

    findMin(arr);

    cout << a_l << ' ' <<  a_r;

}

이거랑은 별개로, 같은 문제인데 이번에는 용액 3개를 가지고 푸는 버전도 존재한다.
세 용액

아무래도 이 문서가 도움이 될 것 같다.
triplet sum

보면 세 가지 방법을 알려주는데, 하나는 브루트포싱이라 뭐... 의미가 없고, 하나는 투 포인터, 마지막은 해싱이다.

투 포인터 방법도 근데 뭐 크게 다른 건 없는 게, 왼쪽에 원소를 하나 고정해 둔 다음에 그 오른쪽 원소들을 위에서 투 포인터로 푼 것처럼 옮겨가면서 가운데에서 만날 때까지 하고, 그 다음 왼쪽 원소를 한 칸 오른쪽으로 옮겨서 또 하고, 또 왼쪽 원소를 오른쪽으로 옮기고... 의 반복이다. 원소가 n개라고 할 때, 왼쪽 원소를 옮기는 게 O(N)이고, 또 포인터 연산이 O(N) 걸리니까 시간복잡도는 O(N^2)가 될 것이다. 그래도 다항식 시간으로 끊기니까 다행인가...

세 번째 방법은 엄밀히 말하면 위 문제를 푸는 데 사용할 만한 방법은 아니고, 그냥 뭐... 위랑 대단하게 다를 건 없다. 차이라면 뭐 원소 찾느라 set 쓴다? 근데 이것도 이 문제에서는 0이 되는 케이스를 찾는 게 아니라 0이랑 가까운 케이스를 찾는 거라서... 일일히 또 탐색하면 n^3 되니까 걍 투 포인터 변형으로 푸는 게 나을 것 같다.

아무튼 그렇다. 이 문제도 한 번쯤 풀어봐야겠다. 대신 인풋 범위 보니까 2개까지는 21억 안 넘는데 3개부터는 넘을 수 있으니까 자료형 좀 주의하고.

profile
학부생

0개의 댓글

Powered by GraphCDN, the GraphQL CDN