[BOJ 백준] 2467번 - 용액

www.acmicpc.net/problem/2467

2467번: 용액

 

 

이전의 문제 두 용액(paris-in-the-rain.tistory.com/59)에서는 절댓값 대소 비교로 문제를 풀었다.

두 문제의 차이는 정렬 여부인데, 두 용액 문제는 정렬이 안되어 있고, 이 문제는 정렬이 되어있다.

 

이 문제는 투포인터를 활용했다.

포인터의 시작점을 맨 처음 인덱스(p1), 맨 끝 인덱스(p2)로 두었다.

 

해당 인덱스의 숫자를 더하여 값을 확인한다. 두 숫자를 더해서 0에 가까운 값을 찾는 것이므로 절댓값 비교를 했다.

 

포인터를 이동하는 기준은 아래와 같다.

• 두 숫자의 합이 양수인 경우 : 맨 끝 인덱스 한 칸 앞으로 (p2--)
• 두 숫자의 합이 음수인 경우 : 맨 앞 인덱스 한 칸 뒤로 (p1++)

 

 

소스코드

#include<bits/stdc++.h>
#define endl "\n"
#define MAX 10
using namespace std;
int n;
vector<int>v;
int main() {	
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//freopen("input.txt", "r", stdin);
    cin>>n;
    for(int i=0; i<n; i++){
        int t; cin>>t;
        v.push_back(t);
    }

    int p1 = 0;
    int p2 = n-1;
    int answer = 2000000005; // 0에 가깝다 : 절댓값이 가장 작다
    int ans_p1 = 0;
    int ans_p2 = 0;
    while(p1<p2){
        int res = v[p1] + v[p2];
        if(answer > abs(res)){
            ans_p1 = p1;
            ans_p2 = p2;            
            answer = min(answer, abs(res));
        }
        if(res<0){
            p1++; 
        }
        else if(res>0){
            p2--; 
        }
        else{
            cout<<min(v[ans_p1], v[ans_p2])<< ' '<<max(v[ans_p1], v[ans_p2]);
            return 0;
        }
    }
    cout<<min(v[ans_p1], v[ans_p2])<< ' '<<max(v[ans_p1], v[ans_p2]);
	return 0;
}