백준 2467 - 용액(C++)

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

2467번: 용액

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

투포인터는 조건에 따라 양쪽 끝을 하나씩 줄여가면서 원하는 값을 찾는 방법입니다.

 

2개의 용액을 선택해 두 수의 차의 최솟값(절댓값)을 구하는 문제입니다.

그렇다면 크기 순으로 정렬한 뒤, 가장 큰 수와 가장 작은 수를 선택하면서 시작합니다.

그 후, 조건에 따라 자신보다 큰 수 혹은 작은 수를 선택해가면 답이 나올 것입니다.

 

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

 

 

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

#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(){
    int start = 0, fin = N-1;
    LL left = arr[0], right = arr[N-1];
    LL sum = left + right;
    while(start < fin){
        LL Next = arr[start] + arr[fin];
        if(abs(sum) > abs(Next)){
            sum = Next;
            left = arr[start];
            right = arr[fin];
        }
        if(Next <= 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;
}

 

 

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