[백준 BOJ] 2473 세 용액 C++

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

 

 

2470 두 용액 문제의 응용이다.

 

•  입력
  • 첫째줄: 전체 용액의 수 N (3 <= N <= 5000)
  • 둘째줄: 용액의 특성값 (-10^9 ~ 10^9)
• 출력
  • 특성값을 0에 가깝게 만드는 세 용액의 특성값 출력 (오름차순으로)

---

풀이1️⃣ - 시간초과

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#define INF 987654321
using namespace std;

int N;
vector <int> v;
vector <int> answer;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;
    int a;
    for (int i=0;i<N;i++){
        cin >> a;
        v.push_back(a);
    }

    sort(v.begin(), v.end());

    int zero=INF;
    for (int i=0;i<N;i++){
        for (int j=i+1;j<N;j++){
            for (int k=j+1;k<N;k++){
                int sum = v[i] + v[j] + v[k];

                if (abs(sum) <= abs(zero)){
                    answer.clear();
                    answer.push_back(v[i]);
                    answer.push_back(v[j]);
                    answer.push_back(v[k]);
                    zero = sum;
                    break;
                }
            }
        }
    }

    for (int i=0;i<3;i++){
        cout << answer[i] << " ";
    }

    return 0;
}

주어진 용액의 특성값을 정렬하고 투포인터를 사용하여 구하려 했으나 3중 for문을 사용하면 더 수월하게 해결할 수 있을거라는 생각에 3중 for문을 사용했다. 그랬더니 시간초과가 나왔다. O(N^3)이라 5000^3을 수행해야 해서 이런 결과가 나온 것 같다. 

그래서 처음에 생각했던 3개의 지점을 가리키는 방법을 적용해보았다.

---

 

풀이2️⃣ - 오답

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#define INF 987654321
using namespace std;

int N;
vector <int> v;
vector <int> answer(3);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;
    int a;
    for (int i=0;i<N;i++){
        cin >> a;
        v.push_back(a);
    }

    sort(v.begin(), v.end());

    long long zero=INF;
    long long sum=INF;
    for (int first=0;first<N-2;first++){
        int second = first+1;
        int third = N-1;

        while (second < third){
            sum = (long long)v[first] + (long long)v[second] + (long long)v[third];

            if (abs(sum) <= zero){
                zero = abs(sum);
                answer.clear();
                answer.push_back(v[first]);
                answer.push_back(v[second]);
                answer.push_back(v[third]);
            }

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

    for (int i=0;i<3;i++){
        cout << answer[i] << " ";
    }

    return 0;
}

절반 정도에서 '틀렸습니다'가 나왔다. 의심이 가는 곳은 zero와 sum의 초기값이었다. 첫번째 코드에서는 zero와 sum의 자료형을 int로 설정했으나 특성값이 범위가 10억이기에 long long으로 자료형을 변경했던 것을 떠올렸고, 세 용액의 합이 -30억에서 +30억까지 나올 수 있다는 것을 고려해 zero의 초기값을 변경했다.

 

 

풀이3️⃣ - 정답

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#define INF 987654321
using namespace std;

int N;
vector <int> v;
vector <int> answer(3);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;
    int a;
    for (int i=0;i<N;i++){
        cin >> a;
        v.push_back(a);
    }

    sort(v.begin(), v.end());

    long long zero=3000000000LL;
    long long sum=0;
    for (int first=0;first<N-2;first++){
        int second = first+1;
        int third = N-1;

        while (second < third){
            sum = (long long)v[first] + (long long)v[second] + (long long)v[third];

            if (abs(sum) < zero){
                zero = abs(sum);
                answer.clear();
                answer.push_back(v[first]);
                answer.push_back(v[second]);
                answer.push_back(v[third]);
            }

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

    for (int i=0;i<3;i++){
        cout << answer[i] << " ";
    }

    return 0;
}