백준 2473 - 세 용액

안 궁금하시겠지만 사진 속 잘생긴 분의 존함은 세용님입니다

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

2473번: 세 용액

0.

용액의 특성값이 뒤죽박죽 섞여있기 때문에 우선 배열을 오름차순으로 정렬한다.

정렬한 뒤 우리가 가장 먼저 떠올릴 수 있는 풀이는 아래와 같은 삼중반복문을 통한 브루트포스 알고리즘일 것이다.

...
for(int e = 2; e < N; e++) {
	for(int s = 0; s < e - 1; s++) {
    	for(int m = s + 1; m < e; m++) {
        	//특성값의 최댓값은 10억이므로, 3개를 더하면 int 자료형은 오버플로우 발생 위험
        	mn = min(mn, 0ll + v[s] + v[m] + v[e]);
            ...
        }
    }
}
...

삼중 반복문을 돌리면 대략 O(N^3), 즉 5000^3 = 125,000,000,000 >> 10^8의 연산이 요구되므로 시간 초과에 빠진다.

이제 우리가 해야할 일은 맨 안쪽의 반복문을 최대한 단순화하여 시간복잡도를 대략 O(N^2 * log(N))으로 단축시키는 것이다!

 

1.

예제 2번의 입력을 정렬한 배열은 다음과 같다.

-24 -6 -3 -2 61 98 100

s = 0, e = 3일 때, 즉 v[s] = -24, v[e] = -2일 때, 0 < m < 3인 m에 대해 v[s] + v[m] + v[e]가 0에 근접하려면 어떻게 해야할까? 직관적으로, 고정된 값 v[s]와 v[e]가 음수이므로, 움직일 수 있는 v[m]이라도 가장 작은 음의 값을 갖게 해야 한다. 따라서, v[s]와 v[e]가 모두 음수일 경우, 굳이 내부에서 반복문을 돌리지 않아도 m의 위치가 가능한 범위 중 가장 오른쪽인 e - 1가 됨을 알 수 있다.

 

또한 배열 v는 이미 정렬이 되었으므로 v[e]가 음수이면 v[s] 또한 반드시 음수이다. 결국 s, e에 대해 v[e]가 음수이면 세 용액의 특성값은 반드시 v[s] + v[e-1] + v[e]이다.

 

같은 원리로, v[s]가 양수이면 세 용액의 특성값은 반드시 v[s] + v[s + 1] + v[e]이다.

 

2.

그렇다면 위 두 경우를 만족하지 않을 때, v[s]는 음수지만 v[e]는 양수일 때는 어떻게 해야할까?

|v[s] + v[m] + v[e]|가 최소가 되려면 v[m] + (v[s] + v[e]) == v(m) - -(v[s] + v[e])가 0에 가까워야 한다. 여기서 우리는 이분탐색을 사용할 수 있다. 이분탐색을 통해 -(v[s] + v[e])보다 크거나 같은 원소 중 가장 작은 원솟값 v[m]을 찾는다.

 

이분탐색의 조건을 v[m]이 -(v[s] + v[e])보다 크거나 같은가?라고 할 때, s < i < e인 인덱스들에 대해 해당 조건문에 대한 결과는 이런 식으로 나타날 것이다.

 

F F F .... F F T T ... T

이제 TF값과 세 용액의 특성값을 그래프 상에 나타내보자.

우리가 찾는 값은 세 용액의 특성값, 즉 노란 직선 그래프의 y값이 0에 가장 인접한 m의 위치이다. 그래프를 보면 알 수 있듯이 빨간색 T를 기준으로 오른쪽으로 이동할수록 y값이 0에서 멀어지며, 파란색 F를 기준으로 왼쪽으로 이동할수록 0에서 멀어진다. 따라서 m이 위치할 수 있는 인덱스는 파란 F, 빨간 T 중 y값이 더 작은 인덱스이다.

 

3. 구현

투 포인터를 이용해 양 끝 v[s], v[e]를 고정시킨 뒤 그 값에 따라 특성값이 최소가 되는 v[m]을 구한다. 투 포인터라는게 꼭 별게 아니고 두 개의 인덱스를 적절히 움직여가며 문제를 해결하는 풀이법이 모두 투 포인터에 속한다고 보면 된다.

for (e = 2; e < N; e++) {

    for (s = 0; s < e - 1; s++) {
        //v[e]가 음수일 경우
        if (v[e] < 0)
            m = e - 1;

        //v[s]가 양수일 경우
        else if (v[s] > 0)
            m = s + 1;

        //v[s]는 음수, v[e]는 양수일 경우
        else {
            //빨간색 T
            m = lower_bound(v.begin() + s + 1, v.begin() + e - 1, -(v[s] + v[e])) - v.begin();

            //파란색 F와 비교해 절댓값이 더 작은 쪽 선택
            if (m > s + 1 && abs(v[s] + v[m] + v[e]) > abs(v[s] + v[m - 1] + v[e]))
                m--;
        }

        //합 구해서 비교, 최솟값 위치 저장
        sum = abs(0ll + v[s] + v[m] + v[e]);
        if (mn > sum) {
            ans1 = v[s]; ans2 = v[m]; ans3 = v[e];
            mn = sum;
        }
    }
}

cout << ans1 << ' ' << ans2 << ' ' << ans3 << '\n';

* 마지막 case에서 사용한 lower_bound는 이분탐색과 유사하게 작동하며, 정렬된 구간에서 argument3보다 크거나 같은 값 중 최솟값의 반복자를 반환한다. 해당 반복자에서 시작 반복자를 빼주면 인덱스를 얻을 수 있다. 익숙하지 않으면 이분탐색을 사용해도 된다.