[C++] BOJ 2473 - 세 용액

BOJ 2473 - 세 용액 (https://www.acmicpc.net/problem/2473)

01. 🔎 문제 탐색

N: 전체 용액의 수 (3 <= N <= 5,000)
산성 용액 (1 ~ 1e9)
알칼리성 용액 (-1e9 ~ -1)

 

* 서로 다른 용액 3가지를 혼합하여 특성값이 0에 가까운 혼합 용액을 만드는 세 용액의 특성값 출력

 

같은 종류(산성, 알칼리성)만 혼합 가능
하지만, 같은 특성 값을 가지는 용액을 중복하여 혼합할 수는 없음

01-1. 가능한 시간 복잡도

• N의 최대가 5,000으로 시간 복잡도가 O(N^2 log N) 이하로 구현 가능

01-2. 알고리즘 선택

• 투 포인터로 구현할 경우, 시간 복잡도가 O(N^2)으로 구현가능
• 이분 탐색으로 구현할 경우, 시간 복잡도가 O(N^2 log N)으로 구현 가능

02. 📝 코드 설계하기

[투 포인터]

1. N과 특성 값을 N개 입력
2. 입력된 특성 값을 오름차순으로 정렬
3. 특성 값 하나를 고정시켜두고, 뒷 범위에서 투 포인터로 최적의 조합 탐색
4. 혼합 용액의 특성 값이 현재 최소 특성 값보다 작을 경우, 값을 갱신하고 용액 3가지를 배열에 저장

[이분 탐색]

1. N과 특성 값을 N개 입력
2. 입력된 특성 값을 오름차순으로 정렬
3. 특성 값 2개(i, j)를 이중 반복문으로 N-2까지 탐색
4. 특성 값 2개를 합하고 부호를 바꾼 값을 target이라 정의
5. 나머지 특성 값 하나는 j+1부터 N-1까지 이분 탐색을 통해 target을 탐색
6. 혼합 용액의 특성 값이 현재 최소 특성 값보다 작을 경우, 값을 갱신하고 용액 3가지를 배열에 저장

03. 🛠️ 시도별 수정

1회차

• 투 포인터에서 3 용액의 합이 0일 때를 처리해주지 않아 무한 루프됨 -> 수정

---

04. 🗝️ 정답 코드

[투 포인터]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

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

  int N;
  vector<ll> v;

  cin >> N;
  for(int i = 0; i < N; i++){
    int tmp;
    cin >> tmp;
    v.push_back(tmp);
  }
  sort(v.begin(), v.end());

  ll best_val = LLONG_MAX;
  int result[3];

  for(int mid = 0; mid < N-2; mid++){
    int start = mid+1, end = N-1;
    while(start < end){
      ll cur_val = v[start] + v[mid] + v[end];

      if(llabs(cur_val) < best_val){
        best_val = llabs(cur_val);
        result[0] = v[mid];
        result[1] = v[start];
        result[2] = v[end];
      }

      if(cur_val < 0) start++;
      else end--;
    }
  }

  sort(result, result + 3);
  for(auto& e : result) cout << e << " ";

  return 0;
}

[이분 탐색]

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
  int N;
  vector<ll> v;

  scanf("%d", &N);
  for(int i = 0; i < N; i++){
    ll tmp;
    scanf("%lld", &tmp);
    v.push_back(tmp);
  }
  sort(v.begin(), v.end());

  ll best_val = LLONG_MAX;
  ll result[3];
  for(int i = 0; i < N-2; i++){
    for(int j = i+1; j < N-1; j++){
      ll target = -(v[i] + v[j]);

      int left = j+1, right = N-1;
      while(left <= right){
        int mid = (left + right) / 2;
        ll cur_val = v[i] + v[j] + v[mid];

        if(llabs(cur_val) < best_val){
          best_val = llabs(cur_val);
          result[0] = v[i];
          result[1] = v[j];
          result[2] = v[mid];
        }

        if(v[mid] < target) left = mid + 1;
        else right = mid - 1;
      }
    }
  }

  sort(result, result+3);
  for(auto& e : result) printf("%lld ", e);

  return 0;
}