[BOJ] 2473 세 용액

3-SUM 알고리즘을 이용하여 문제를 풀 되, 정확한 조합이 아닌 가장 가까운 답을 찾는 것이 목표이다.

고로 합산한 결과 값 중 현재 최소인 조합의 결과를 저장해야 한다. 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int a, b, c;
long long N, temp, best = LLONG_MAX;
vector<long long> val;

int main(){
  cin >> N;
  for (int i = 0 ; i < N ; i++){
    cin >> temp;
    val.push_back(temp);
  }
  
  sort(val.begin(), val.end());
  
  for(int first = 0 ; first < val.size() - 2; first++){
    int second = first + 1;
    int third = N - 1;

    while(second < third){
      long long result = val[first] + val[second] + val[third];
      if( abs(result) < abs(best) ){
        best = abs(result);
        a = first;
        b = second;
        c = third;
      }

      if(result < 0) second++; else third--;
    }
  }

  cout << val[a] << " " << val[b] << " " << val[c] << endl;
  return 0;
}

 

알고리즘 자체는 한번 이해하면 매우 단순한 편이다.