[파이썬/python] 백준 - 2295 세 수의 합

문제

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

---

문제 설명

1. N개의 자연수들로 이루어진 집합 U가 있다.
2. 집합 U에서 세 개의 수를 골라 그 합이 U 집합에 존재한다면 그 합이 가장 큰 경우를 찾는다.
   1. 세 개의 수 x,y,z는 중복이 가능하다.    

 

---

풀이

집합 U의 최대 크기는 N의 최대인 $10^3$이다.

세 개의 수가 들어갈 수 있는 모든 경우의 수를 탐색하려면 $N^3 = 10^9$이므로 시간초과가 발생한다.

따라서 특수한 방법을 통해 시간 소요를 줄여 문제를 해결해야 한다.

 

집합 U가 존재할 때 x,y,z를 세 개의 수, k를 세 수의 합이라고 가정하자. 이 때 x+y+z와 k는 모두 집합에 존재한다.

즉 $x+y+z = k$라는 식을 세울 수 있다.

 

이 식을 약간 변영해보자.$x + y = k - z$ 이 말은 즉, x와 y를 더한 수가 세 수의 합 k에서 z를 뺀 수와 동일하다는 것이다.

따라서 $x+y+z$가 집합에 존재하는지 확인할 필요 없이 $x+y$를 모두 구한 후 $k-z$와 동일한지 검사하면 문제의 해답을 구할 수 있다. 그렇다면 시간복잡도는 $2*N^2$가 되기 때문에 충분히 여유롭게 문제를 해결할 수 있을 것이다.  

 

1. arr 배열에 x+y의 모든 경우의 수를 더한다. 중복을 제거하기 위해 set()을 사용했다.
2. k-z를 계산하여 arr배열에 존재하는지 확인 후 존재한다면 k의 최댓값을 갱신한다. 
3. 최댓값 K를 출력한다.

---

코드

import sys
input = sys.stdin.readline

arr = set()

n = int(input())
lst = []
for i in range(n):
    lst.append(int(input()))
lst.sort()
 
for x in range(n):
    for y in range(n):
        arr.add(lst[x]+lst[y])

res = 0
for k in range(n-1,-1,-1):
    for z in range(n-1,-1,-1):
        if lst[k]-lst[z] in arr:
            res = max(lst[k],res)
print(res)

---

시간복잡도

• $x+y$계산시 $N^2$, $k-z$  계산 시 $N^2$ 즉 $2*N^2$ 따라서 총 $2*N^2$이다.
• 시간복잡도는 약 $O(2*10^6)$이다.