알고리즘
[백준] 세 수의 합 - python
hseoky
2024. 10. 12. 14:20
728x90
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()
728x90