[백준/c++] 2479번: 두 용액

https://www.acmicpc.net/problem/2470

2470번: 두 용액

 

문제 요약

 

같은 양의 두 용액을 혼합한 용액의 특성 값은 혼합에 사용된 각 용액의 특성 값의 합으로 정의한다. 

같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.

두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성

 

범위

 

전체 용액의 수 N (2 이상 100,000 이하)

용액의 특성 값 (-1,000,000,000 이상 1,000,000,000 이하)

 

 

 

---

 

 

이 문제는 두 포인터 혹은 이분 탐색으로 풀 수 있다. 나는 두 포인터로 문제를 풀었다.

처음에는 혹시나 완전탐색으로 할 수 있는지 입력 범위를 찾아보았는데 최대 N 100,000 인 것을 보고 포기했다. (N^2 = 10,000,000,000로 시간 초과🚨)

 

L과 R을 사용해서 두 용액을 가리키도록 했는데 L과 R은 더할 수 있는 가능한 용액의 최대, 최소값으로 정했다. 두 용액을 합해서 0에 가장 가깝게 나오려면 해당 값의 반대 부호값을 더하면 된다. 그렇다면 다른 용액의 값이 그 반대 부호 값과 가장 가까워야 하는데 입력 배열 속 가장 큰 값을 더해보면서 점차 줄이는 방향으로 하면 될 것 같다고 생각했다.

우선, L과 R의 절대값을 구해서 현재 최소합과 비교를 했다. 만약 더 작다면 최소합은 업데이트된다. 이후, L 혹은 R의 범위를 옮겨줘야 한다. 

 

• L + R <= 0
  
  
  • 최소값(L)최솟값(L) 입장에서 가장 작은 합이다. (앞으로 당겨지는 다른 최댓값(R--)과의 합보다 작음) 그러므로 이 원소는 끝이 나고 최솟값(L)을 변경해준다 ➿ L++
• L + R > 0
  
  
  • 최댓값(R) 입장에서 가장 작은 합이다. (뒤로 당겨지는 다른 최솟값(L++)과의 합보다 작음) 그러므로 이 원소는 끝이 나고 최댓값(R)을 변경해준다. ➿ R--

 

가장 작은 합을 구하고, 해당 L과 R을 출력해준다.

 

//두 포인터
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int n, a[100001];

void input(){
    cin >> n;
    for(int i=0; i<n; i++) cin >> a[i];
}

void solution(){
    sort(a, a+n); //sorting
    int sum = 2000000001, L = 0, R =n-1, ans1=0, ans2=0;
    
    while(L<R){ //원소가 하나남은 경우는 포함되지 않으므로 '<'
        if(sum > abs(a[L] + a[R])){ //min value
            sum = abs(a[L] + a[R]); //update
            ans1 = L;
            ans2 = R;
        }
        a[L]+a[R] > 0 ? R-- : L++;
    }
    
    cout << a[ans1] << ' ' << a[ans2] << '\n';
    
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}

 

4번의 시도만에 성공...

 

 

처음에는 이분탐색으로 풀어보려고 했지만, 계속 머릿속에서 얽히는 바람에 두 포인터로 다시 풀었다.

꼭 다시 풀어보아야겠다.

 

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!