Baekjoon(백준) 2470번 - 두 용액

백준 사이트의 2470번.
문제 제목 : 두 용액
백준 2470

한국정보올림피아드 (KOI) 2010년도 중등부 1번 문제이다.

문제 해석

문제를 보면 스토리는 거창하게 적혀있는데 그냥 N개의 서로 다른 정수가 주어지면 그 중에 두 수를 더한 값이 0에 가장 가까운 경우, 그 두 수를 출력하는 문제이다. 답이 여러 가지가 가능할 수도 있기 때문에 스페셜 저지가 적용된 문제이다.

풀이 전략

바로 떠오르는 풀이법은 역시나 brute force 가 될 것이다. 나올 수 있는 모든 합을 다 계산해서 절댓값이 가장 최소인 두 수를 고르면 된다. 연산량을 계산해보면 ${}_n \mathrm{C}_2$ 이므로 약 50억 번의 최대 연산량이 나온다. 시간 제한 1초라서 바로 시간 초과 뜬다.

그러면 어떻게 할까? 우리가 특정값 또는 그 특정값에 가장 가까운 값을 찾을 때 시간을 줄이는 방법이 있다. 바로 binary search 이다.
binary search 는 인터넷에 검색만 하면 좋은 설명 자료들이 많이 나온다. 간략하게만 설명하자면 left와 right 두 지점이 있고 각각 정렬된 배열의 첫 index와 끝 index를 가리키도록 설정한다. 이 후 $\frac{left + right}{2}$ 한 것 (중간값의 index) 을 mid 라 하면, mid가 가리키는 배열의 값이 목표하는 값보다 큰지 작은지 비교한다. 크다면 right를 mid로 설정하고, 작다면 left를 mid로 설정한 후 똑같은 과정을 반복한다. left와 right가 서로 같아질 때까지 반복하면 된다.

구현

binary search를 그럼 어떻게 이용할까? binary search는 주어진 배열이 오름차순으로 정렬되어 있을 때 적용가능하다. 그 점을 유의하면 다음과 같이 구현하면 된다.

1. 주어진 배열 입력받고 오름차순 정렬
2. 각 정수 N개를 처음부터 스캔하면서 각 정수 $x$ 에 대해 $-x$ 를 목표값으로 설정하고 각각 binary search를 돌려서 $-x$에 가까운 수를 찾는다.
3. 찾은 수와 $x$를 더해서 그 값이 최소값이면 답과 최소값을 갱신해준다.
4. 답 출력

binary search가 주어진 배열이 N개 일 때 시간복잡도가 O($\log_2 N$ ) 이다. 따라서 총 시간복잡도는 O($N\log_2 N$) 이다. $N=100000$ 일 때도 연산수가 1억번을 넘지 않는다.
솔루션 코드는 github에 있다.

baekjoon 2470 solution code