[BOJ] 2473번 : 세 용액

• 문제 설명

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

2473번: 세 용액

KOI 2010 고등부 1번 문제이다.

 

푸는 방법은 두 가지가 있는데, two pointers로 푸는 방법과 binary search로 푸는 방법이 있다. two pointers로 풀면 time complexity는 O(N^2)으로 풀 수 있고, binary search로 풀면 O(N^2*logN)으로 풀 수 있다. 다만 two pointers로 풀기 위해서는 정당성 증명이 필요하고 떠올리기 더 어렵다.

 

 

• Binary search를 이용한 방법

입력받은 특성값을 정렬한다. N의 upper bound가 5000이므로, 두 개의 특성값을 이중 for문을 이용해서 잡는다.(N^2) 이 두 개의 특성값을 기준으로 최소값을 만드는 특성값을 binary search를 이용해 찾는다.(logN) 떠올리기는 간편하나 구현은 귀찮은 편이다. 

 

간단한 아이디어이므로 특별히 첨할 말은 없다.

 

binary search를 이용한 비슷한 방법으로 당해년도 KOI 초등부 1번, 중등부 1번도 해결할 수 있다. 이 문제들은 N의 upper bound가 10만이므로 아래의 방법으로는 해결할 수 없다. 

 

• two pointers를 이용한 방법

입력받은 특성값을 정렬한다. 한 개의 특성값을 for문을 이용하여 잡고,(N) 잡은 특성값의 index가 i일 때, left pointer를 i+1로 잡고, right pointer를 n(구현에 따라 n-1)으로 잡은 후 세 특성값의 합이 0보다 작으면 left++, 0보다 큰 경우 right--를 해준다. (N)

 

방법과 구현은 간단하지만 정당성을 증명하려면 조금 생각을 해야 한다.

 

• two pointers 방법의 정당성 증명

이 알고리즘이 정답을 낼 수 있는 이유는 다음과 같이 보일 수 있다. 만약 전체 N개 중 i, j, k번째를 선택하였을 때 특성값을 0에 가장 가깝게 만들 수 있다고 해 보자.

 

index	1	...	i	...	j	...	k	...	n
	value[1]		value[i]		value[j]		value[k]		value[n]

for문으로 돌리는 index가 i가 아니라면 어차피 최적 특성값을 만들 수 없으므로 for문으로 돌아가는 index가 i가 될 때까지 진행된다. for문의 index가 i가 되었을 때에는 i+1이 left가 되고, n이 right가 된다. 이때 특성값의 합이 몇이 되었든 두 pointers가 서로 만날 때까지 loop는 계속된다. 따라서 left가 j에 도달하거나 right가 k에 도달하는 상황 중 하나가 반드시 발생한다.

 

만약 left pointer가 j에 도달한 상황이 발생했다고 해 보자. 이 경우 value[i]+value[j]+value[right]가 양수인 상황과 음수인 상황으로 나누어 생각해 볼 수 있다.

 

양수인 경우 right 포인터는 감소한다. 이때 right 포인터는 반드시 k보다 크거나 같은 위치에 놓여있게 될 수 밖에 없는데, 만약 그 전에 right 포인터가 k보다 작은 위치에 놓여있었다면 value[i]+value[j-a]+value[k]가 0보다 컸다는 의미가 된다. value[i]+value[j-a]+value[k]는 value[i]+value[j]+value[k]보다 작으므로 0보다 크면서 최적값보다 작은 양수는 최적값보다 더 0에 가까운 양수이다. 따라서 전제와 모순되므로 right 포인터는 반드시 k보다 크거나 같은 위치에 놓일 수 밖에 없다.

 

음수인 경우 value[i]+value[j]+value[k+b]보다 value[i]+value[j+a]+value[k+b]가 더 absolute값이 0에 가깝다는 이야기가 된다. 이 역시도 전제에 어긋나는데, 이 경우 value[i]+value[j]+value[k+b]는 0보다 작은데 이보다 더 작은 value[i]+value[j]+value[k]가 최적값이 될 수 없기 때문이다. 따라서 이러한 경우는 존재할 수 없다.

 

같은 방법으로 right가 먼저 k에 도달한 상황에 대해서도 left pointer가 j보다 큰 값을 가리킬 수 없음을 증명할 수 있고, 모든 경우 최적의 해를 얻을 수 있음을 보일 수 있다.

 

 

• two pointers 방법의 구현

for(int i = 0 ; i<n-2; i++) {
        left = i+1, right = n-1;
        while(left<right) {
            sum = value[i]+value[left]+value[right];
            
            if(abs(sum)< abs(bestSum) ) {
                bestSum=sum;
                best[0]=value[i],best[1]=value[left],best[2]=value[right];
            }
            if(sum>=0) right--;
            else if(sum<0) left++;
        }
    }
}

 

핵심적인 아이디어의 for문이다. i를 for문으로 돌리고, left와 right라는 두 개의 pointers를 돌리면서 셋의 합인 sum의 absolute값이 더 작다면 갱신한다.

 

전체 코드는 내 github에서 볼 수 있다.

 

https://github.com/Jordano-Jackson/PS/blob/main/BOJ/2473/2473.cpp

GitHub - Jordano-Jackson/PS: Problem solving