백준 2473 - 세 용액(C++)

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

2473번: 세 용액

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

https://junseok.tistory.com/314 -> 이 문제에서 조건이 하나 추가된 문제입니다.

 

두 용액이 아닌, 3개의 용액을 선택해 값이 최소가 되는 것을 구하는 문제입니다.

두용액이였다면, 간단한 투포인터를 이용해 풀 수 있겠지만, 용액이 3개이기에 일반적인 방법으로 풀 수는 없었습니다.

 

가장 간단하게 생각할 수 있는 방법은 용액을 하나 미리 선택하고 구하는 방법입니다.

즉, 용액을 하나 고정한 뒤, 남은 두 용액을 투포인터를 통해 구하는 것입니다.

 

저는 for문을 이용해 1~N번까지의 용액을 미리 선택했습니다.

선택한 용액을 정해야하는데, 저는 중간 크기의 용액으로 고정했습니다. (작은 혹은 큰 용액으로 해도 괜찮습니다.)

 

그렇다면, 작은 용액과 큰 용액은 중간 용액과 값이 겹치면 안됩니다.

따라서 투포인터를 할 때, 조건이 추가됩니다.

1. 큰 용액에서 범위를 줄일 때, 중간 용액과 같아진다면?

-> 큰 용액은 최대한 줄었음으로 작은 용액을 늘린다. 작은 용액을 늘릴 수 없는 경우는 더 이상 탐색을 할 수 없는 경우이다.

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
#define INF 9876543210
using namespace std;

int N;
int arr[5001];
LL Sum = INF, Left, Right, Mid;

void solve(){
    sort(arr, arr+N);
    for(int i = 0; i < N; i++){
        LL middle = i, start, fin;
        if(i == 0) {
            start = 1; 
            fin = N-1; 
        }
        else if(i == N-1){
            start = 0;
            fin = N-2;
        }
        else{
            start = 0;
            fin = N-1;
        }
        LL left = arr[start], right = arr[fin], mid = arr[middle];
        LL sum = left + mid + right;
        while(start < fin){
            LL Next = arr[start] + mid + arr[fin];
            if(abs(sum) > abs(Next)){
                sum = Next;
                left = arr[start];
                right = arr[fin];
            }
            if(Next > 0){
                if(fin - 1 == middle) {
                    if(start - 1 < middle) start++;
                    else break;
                }
                else fin--;
            }
            else{
                if(start + 1 == middle){
                    if(fin-1 > middle) fin--;
                    else break;
                }
                else start++;
            }
        }
        if(!(left < mid && mid < right)) continue;
        if(abs(Sum) > abs(sum)){
            Sum = sum;
            Left = left;
            Mid = mid;
            Right = right;
        }
    }
    
    cout << Left << " " << Mid << " " << Right;
}

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

 

 

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