백준 14921번 [용액 합성하기](C++) -yes6686- 티스토리

백준 문제 풀이: 14921 (용액 합성하기)

---

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

문제 설명:

양의 용액과 음의 용액을 섞어 두 용액의 합이 0에 가장 가깝게 만드는 문제입니다. 여러 개의 용액 중 두 용액을 선택했을 때, 합의 절댓값이 최소가 되는 경우를 찾습니다.

---

문제 해결 코드

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

int arr[100001];

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

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

    // 양수만 있는 경우: 첫 두 용액의 합이 최소
    if (arr[0] >= 0) {
        cout << arr[0] + arr[1] << '\n';
    } 
    // 양수와 음수가 섞여있는 경우: 투포인터 활용
    else {
        int s = 0; // 시작 포인터
        int e = n - 1; // 끝 포인터
        int minAns = 2e9; // 초기 최소값 설정 (최대 범위 이상)

        while (s < e) {
            int sum = arr[s] + arr[e];

            // 현재 합의 절댓값이 더 작다면 갱신
            if (abs(minAns) > abs(sum)) {
                minAns = sum;
            }

            // 합이 양수라면 오른쪽 포인터를 왼쪽으로 이동
            if (sum > 0) {
                e--;
            }
            // 합이 음수라면 왼쪽 포인터를 오른쪽으로 이동
            else {
                s++;
            }
        }
        cout << minAns;
    }
}

---

코드 설명

• 양수만 있는 경우: - 배열이 양수로만 이루어진 경우, 두 수의 합이 최소가 되므로 첫 번째와 두 번째 용액을 더합니다.
• 투 포인터 알고리즘: - 두 개의 포인터를 사용해 배열의 양 끝에서 시작합니다.
• 포인터 이동 조건: - 두 용액의 합이 양수인 경우: 오른쪽 포인터를 왼쪽으로 이동합니다. - 두 용액의 합이 음수인 경우: 왼쪽 포인터를 오른쪽으로 이동합니다.
• 최소값 갱신: - 각 단계에서 합의 절댓값을 비교하여 더 작은 값으로 갱신합니다.

---

시간 복잡도 분석

• 투 포인터를 사용하므로 배열을 한 번만 탐색합니다.
• 시간 복잡도는 O(N)입니다.

---

입출력 예시

• 입력 예시:

  5  
  -2 4 -99 -1 98

• 출력 예시:

  -1

---

결론

이 문제는 투 포인터를 활용해 최적의 해를 빠르게 찾아낼 수 있습니다. 양수와 음수가 섞여 있는 경우, 두 포인터를 이용하여 최소 합의 절댓값을 효율적으로 구합니다.