백준 2470 - 두 용액(C++)

문제 링크입니다. https://www.acmicpc.net/problem/2470

2470번: 두 용액

투 포인터를 이용하는 문제입니다.

두 개의 용액을 선택해서 최대한 0에 가까운 값을 만드는 문제입니다.

백트래킹으로도 풀 수 있겠지만, N값이 100,000이기에 시간초과가 생깁니다.

 

따라서 이분탐색 중 투 포인터를 통해서 풀어야됨을 알 수 있습니다.

 

투 포인터는 양 끝의 범위를 잡아놓고, 조건에 따라 범위를 좁혀나가는 것을 의미합니다.

해당 문제에서 조건은 두 용액의 합이 양수 or 음수로 나눌 수 있을 것입니다.

 

양 끝값을 더하면서 범위를 줄여나가기에 오름차순 정렬은 필수입니다.

 

처음의 범위는 배열의 시작과 끝입니다.

두 용액을 더한 값이 양수라면, 큰 쪽의 범위를 하나 줄여, 값을 줄여봅니다,

두 용액을 더한 값이 음수라면, 작은 쪽의 범위를 하나 줄여 값을 늘립니다.

 

이를 반복하면서 가장 0에 가까운 값을 찾아줍니다.

 

문제 예시를 통해 확인하겠습니다.

-99

-2

-1

4

98

-99

-2

-1

4

98

-99

-2

-1

4

98

-99

-2

-1

4

98

해당 방법으로 탐색을 이어갑니다.

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>
#define P pair<int,int>
#define PP pair<P, int>
#define F first
#define S second
#define LL long long

using namespace std;

int N;
int arr[100001];

void solve(){
    sort(arr, arr+N);
    int start = 0, fin = N-1;
    LL left = arr[start], right = arr[fin];
    LL sum = left + right;
    while(start < fin){
        LL another_sum = arr[start] + arr[fin];
        if(abs(sum) > abs(another_sum)){
            sum = another_sum;
            left = arr[start];
            right = arr[fin];
        }
        if(another_sum <= 0) start++;
        else fin--;
    }
    cout << left << " " << right;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for(int i = 0; i < N; i++){
	    cin >> arr[i];
	}
	solve();
	return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요