[백준] 2467 - 용액 (C++)

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

각 용액엔 그 용액의 특성을 나타내는 하나의 정수가 주어져 있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의된다. 이 연구소에서는 같은 양의 두 용액을 혼합해 특성값이 0에 가장 가까운 용액을 만들려고 한다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

 

N개의 산성 용액과 알칼리성 용액의 특성값이 정렬된 순서로 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합해 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 2 ≤ N ≤ 100,000
• -1,000,000,000 ≤ 용액의 특성값 ≤ 1,000,000,000 (중복 없음)

 

용액의 특성값은 이미 정렬돼 들어오기 때문에 따로 정렬할 필요는 없다. 두 용액의 특성값의 합이 최대 2,000,000,000을 넘지 않아서 int 범위 안에서 해결할 수 있다.

 

서로 다른 두 용액의 특성값의 합만 신경 쓰면 되기 때문에 left가 right보다 작은 동안에만 투 포인터를 사용해 이분탐색을 진행한다. 두 용액의 특성값의 합이 0에 가장 가까운 두 용액을 찾아야 하기 때문에, 두 용액의 특성값의 합과 그 합의 절댓값을 저장해놓고 left와 right를 조절하면서 반복문이 끝날 때까지 진행해야 한다. 만약 두 용액의 특성값의 합이 0인 경우 더 작은 값은 나올 수 없으므로 해당 두 용액의 특성값을 출력한 뒤 프로그램을 종료한다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. N, 용액의 특성값 정보 입력받기
2. l=0, r=n-1로 놓고 투 포인터를 사용해 이분탐색 진행
   1. 두 용액의 특성값의 합과 그 합의 절댓값을 저장
   2. 두 용액의 특성값의 합이
      1. 0이면 두 용액의 특성값을 출력하고 프로그램 종료
      2. 0이 아니면 절댓값의 최솟값을 찾을 때마다 최솟값과 (출력용) 두 용액의 특성값 저장
         1. 두 용액의 특성값의 합이 0보다
            1. 크면 r 줄이기
            2. 작으면 l 늘리기
3. 조건을 만족하는 두 용액의 특성값 출력

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

#include <iostream>
#include <algorithm>
#define pii pair<int,int>
using namespace std;

int n,li[100001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i=0; i<n; i++) cin >> li[i];

    int l=0,r=n-1,ans=2e9;
    pii p;
    while (l<r) {
        int tmp = li[l] + li[r], ab = abs(li[l] + li[r]);
        if (tmp==0) {
            cout << li[l] << ' ' << li[r];
            return 0;
        }
        else {
            if (ab<ans) {
                ans = ab;
                p = {li[l],li[r]};
            }
            if (tmp>0) r--;
            else l++;
        }
    }
    cout << p.first << ' ' << p.second;
}