[백준, C++] 2467 - 용액

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

2467번: 용액

 

문제 분석

용액들의 특성값이 -10억부터 +10억까지, 오름차순으로 주어진다. 우리는 이 용액들 중 두 용액을 혼합할 것이다. 혼합액의 특성값은 두 용액의 특성값의 합인데, 우리가 찾고자 하는 것은 혼합액의 특성값이 0에 가장 가깝게 하는 두 용액을 찾고자 한다.

 

문제를 읽고 두 개의 포인터를 사용하는 풀이를 생각했다. 용액들의 특성값이 오름차순으로 주어지기 때문에 가장 왼쪽에는 최솟값이 있을 것이고, 가장 오른쪽에는 최댓값이 있을 것이다. 그래서 왼쪽 값과 오른쪽 값을 더해 혼합액을 만들고 혼합액의 특성값에 절대값을 취해 0에 가장 가까워지는 두 용액을 찾도록 하는 것이다. 그리고 이 혼합액의 특성값이 0보다 작은 음수이면 왼쪽 값을 한 칸 오른쪽으로 옮기고, 0보다 큰 양수면 오른쪽 값을 한 칸 왼쪽으로 옮기도록 해 0에 가까워지도록 유도하는 풀이를 생각했다.

 

코드

#include <iostream>
#include <vector>
#define INF 2100000000

using namespace std;

int n;
vector<int> vec;
vector<int> result;

void getInput();
void solve();
void printResult();

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

    getInput();
    solve();
    printResult();

    return 0;
}

void getInput() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        int value;
        cin >> value;
        vec.push_back(value);
    }
}

void solve() {
    int leftIndex = 0;
    int rightIndex = n - 1;
    int minValue = INF;

    while (leftIndex < rightIndex) {
        int sum = vec[leftIndex] + vec[rightIndex];
        
        if (abs(sum) < minValue) {
            minValue = abs(sum);
            result.clear();
            result.push_back(vec[leftIndex]);
            result.push_back(vec[rightIndex]);
        }

        if (sum < 0) {
            leftIndex++;
        } else if (sum > 0) {
            rightIndex--;
        } else if (sum == 0) {
            break;
        }
    }
}

void printResult() {
    cout << result[0] << " " << result[1] << "\n";
}

 

코드 설명

사실 풀이 자체가 매우 간단해서 길게 설명할 건 없을 것 같은데, 풀다가 이상한 게 있어 기록해보고자 한다.

 

나는 이제 INF 값을 21억으로 설정하고 풀 것으로 구상했는데, 처음 문제를 풀 때 21억이 아니라 실수로 2억 1천만으로 설정했다. 그 결과 OutOfBounds라는 런타임 에러가 나왔다.

 

딱히 OutOfBounds가 나올 곳이 없다고 생각했고, 문제를 풀고 어제 약 1시간 가량 + 오늘 일어나서 약 30분가량 계속 이 문제에 대해 생각해봤는데 친구에게 단톡방에 이거에 대해 어떻게 생각하냐고 물어보고 설명하던 도중 런타임에러가 나오는 이유를 알았다.

 

INF값이 영향을 미치는 곳은 minValue의 초기값 설정이다. 즉, minValue의 초기값은 INF로, 만일 INF가 2억 1천만이라면 minValue는 2억 1천만이라는 값을 가지고 시작하게 된다. 그런데 만약 용액의 특성값으로 예를 들어 5억, 6억, 7억이 주어졌다고 하자. 그러면 우리가 출력해줘야할 정답은 5억과 6억이다. 하지만 if (abs(sum) < minValue)의 조건절을 절대 통과할 수 없다. 왜냐면 minValue는 2억따리인데, sum은 11억이나 되기 때문이고 그 결과 result 벡터에 두 용액의 특성값을 push_back하지 않게 된다. 즉 result 벡터는 빈 채로 solve() 메서드가 종료되는데, 그 후 결과를 출력하는 printResult() 메서드에서 비어있는 result 벡터에 대해 result[0]과 result[1]에 접근하기 때문에 OutOfBounds가 발생하는 것이다.