백준/2467번/용액/골드5

Problem Link: https://www.acmicpc.net/problem/2467

문제 설명

Site: Baekjoon
Number: 2467
Category: Binary Search, Two Pointer
Rank: Gold 5

주어진 n개의 용액 중 그 합이 가장 0에 가까운 두 용액을 출력하는 문제입니다.

단순히 이분 탐색을 진행한다면 한쪽으로 치우친 경우 문제를 해결할 수 없기 때문에 투 포인터를 활용하여 문제를 해결하여야 합니다.

기존의 투 포인터와 같이 시작점에 두 포인터를 두고 진행한다면 어느 포인터가 움직일 지 기준을 잡기 애매하여 양쪽 끝에 포인터를 두고 진행합니다.

문제 풀이

1. 최대 10만개의 용액을 저장할 배열 Solution을 선언하고 N개의 용액들을 저장합니다.

2. 양쪽 끝에 포인터를 두고 두 포인터가 서로 맞닿을 때 까지 3개의 과정을 반복합니다.

   a. 두 용액의 합이 기존의 값보다 0에 가깝다면 두 용액을 갱신합니다.

   b. 두 용액의 합이 0이라면 종료합니다.

   c. 두 용액의 합이 0보다 작다면 왼쪽의 포인터를 한칸 위로 올리며, 0보다 크다면 오른쪽의 포인터를 한칸 내립니다.

3. 포인터가 맞닿았다면 저장된 가장 0에 가까운 두 용액을 출력합니다.

#include <iostream>

using namespace std;

int Solution[100001];

// 두 용액이 기존 값보다 0에 가까운지 검사하는 Refresh 함수
void Refresh(int& start, int& end, int& ans1, int& ans2, int& sum, int& summation)
{
	if(abs(sum) > abs(summation))
	{
        sum = summation;
        ans1 = start;
        ans2 = end;
	}
}

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

    int N;
    cin >> N;

    for (int i = 0; i < N; i++)
        cin >> Solution[i];

    int start = 0, end = N - 1, sum = 2147483647, summation = 0;
    int ans1 = start, ans2 = end;

    while(start < end)
    {
        summation = Solution[start] + Solution[end];

        Refresh(start, end, ans1, ans2, sum, summation);

        if (summation == 0)
            break;

        if (summation > 0)
            end--;
        else
            start++;
    }

    cout << Solution[ans1] << ' ' << Solution[ans2];

    return 0;
}