[백준] 세 수의 합 - python

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

난이도: 골드4
알고리즘: 이분탐색

 

풀이과정

---

주어진 수열에서 `x + y + z = k`를 만족하는 x, y, z, k를 선택하는 문제이다. 여기서 x, y, z, k는 중복될 수 있다.

 

가장 먼저 생각했던 방식은 x, y, z를 전수조사를 통해 선택하고,` x + y + z`가 수열에 있는지를 이분탐색을 통해 확인하는 방법이었다.

하지만 이 방법은 `N^3` x `log N` 의 시간 복잡도를 가지고, N = 1000이기 때문에 시간 초과가 발생한다.

 

따라서 y + z를 먼저 계산한 리스트를 만들었다.

y + z를 계산한 리스트는 `N^2`의 시간 복잡도 내에서 만들 수 있다.

 

이제 `x + y + z = k`에서 x와 k를 먼저 선택하고, (k - x)가 위에서 구한 y + z를 계산한 리스트에 있는지를 이분탐색으로 조사 한다.

이 방법은 x와 k를 선택하는 시간복잡도 `N^2`, 그리고 (y + z)에서의 이분탐색을 하는 시간복잡도 `log N^2`의 곱이다.
따라서 전체 시간복잡도는 `O(N^2 x log N^2)`로 주어진 시간 내에 답을 구할 수 있다.

 

소스코드

---

 

import sys
from collections import defaultdict
input = sys.stdin.readline

def binary(target):
    left = 0
    right = len(nums_two) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums_two[mid] == target:
            return True
        elif nums_two[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return False


N = int(input())
nums = []
for _ in range(N):
    nums.append(int(input()))
nums.sort()

# 두 수의 합
nums_two = []
dict = defaultdict(int)
for y in range(N):
    for z in range(y, N):
        cur_sum = nums[y] + nums[z]
        if dict[cur_sum] == 0:
            nums_two.append(nums[y] + nums[z])
        dict[cur_sum] += 1
nums_two.sort()

for k in range(N - 1, -1, -1):
    for x in range(N):
        if binary(nums[k] - nums[x]):
            print(nums[k])
            exit()