Algorithem/백준 PS with code
(python) 백준 #2473 - [G3] 세 용액 : 이진탐색/투포인터
2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 1. O(N*N*logN) : 2개 조합 완탐+바이너리서치 3개의 용액을 고르는 방법을 찾아야한다. 2개의 용액을 완전 탐색으로 고르고, 세 용액의 합이 0에 가장 가까워지도록 하는 마지막 용액을 찾는 방식을 채택했다. 2개의 용액을 완탐으로 찾는데 O(N*N), 마지막 용액을 binary search으로 찾는데 O(logN)이 걸린다. (이진 탐색의 경우 재귀로 푼 경우 시간초과, 반복문으로 푼 경우 성공이었다. 반복문으로 쉽게 짤 수 ..
