백준 2473번 [세 용액](C++) -yes6686- 티스토리

백준 문제 풀이: 2473 [세 용액]

---

문제 링크: https://www.acmicpc.net/problem/2473

문제 설명:

n개의 용액이 주어졌을 때, 세 용액을 혼합하여 그 특성값(합)의 절댓값이 0에 가장 가까운 조합을 찾는 문제입니다. 각 용액은 음수, 0, 양수로 이루어져 있으며, n은 최대 100,000입니다.

---

문제 해결 코드

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

long long int arr[100001];
long long int resultArr[3];

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

    long long int result = 3e9 + 1;
    for (int i = 0; i < n - 2; i++) {
        int k = i + 1;
        int w = n - 1;
        while (k < w) {
            long long int sum = arr[i] + arr[k] + arr[w];
            if (result > abs(sum)) {
                result = abs(sum);
                resultArr[0] = arr[i];
                resultArr[1] = arr[k];
                resultArr[2] = arr[w];
            }
            if (sum < 0) {
                k++;
            } else {
                w--;
            }
        }
    }

    for (int i = 0; i < 3; i++) {
        cout << resultArr[i] << ' ';
    }
}

예제

입력:
5
-2 6 -97 -1 98

출력:
-97 -2 98

---

코드 설명

• 입력 및 정렬:
  • 입력받은 용액 배열을 오름차순으로 정렬합니다. 정렬은 용액 특성값 조합을 효율적으로 탐색하기 위해 필요합니다.
• 이중 포인터를 이용한 탐색:
  • 가장 바깥쪽 반복문에서 첫 번째 용액을 선택합니다.
  • 두 번째와 세 번째 용액은 투 포인터를 사용하여 배열의 나머지 부분에서 절댓값이 가장 작은 특성값 조합을 탐색합니다.
• 결과 갱신:
  • 세 용액의 합이 현재 최솟값보다 작으면 결과를 갱신합니다.
• 출력: 최종적으로 찾은 세 용액을 출력합니다.

시간 복잡도

• 정렬: O(n log n)
• 탐색: O(n^2) (각 첫 번째 용액에 대해 나머지 부분을 투 포인터로 탐색)
• 총 시간 복잡도: O(n^2)

---

결과

이 코드는 세 용액 중 합의 절댓값이 0에 가장 가까운 조합을 정확히 탐색합니다. 투 포인터 기법을 사용하여 효율적으로 동작합니다.