[python] 백준 2295 세 수의 합

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

2295번: 세 수의 합

 

문제 해결

• A[x]+A[y]+A[z] = A[k]를 보고 3개를 잡으려 하지말고 A[x]+A[y] =c= A[k]-A[z]로 바꿔서 생각해보려 하자.
• A[x]+A[y]=c로 가능한 c를 sample 집합에 넣는다.
• k를 가장 큰 n-1인덱스부터 0까지 차례로 고정시키면서 z를 0부터 k인덱스까지 보면서 A[k]-A[z] in sample을 확인하면서 있는 경우 바로 A[k]를 출력하며 문제를 끝낸다.

CODE

import sys
input = sys.stdin.readline
n = int(input())
A = [int(input()) for _ in range(n)]
A.sort()
sample = set()
for x in A:
    for y in A:
        sample.add(x+y)
def solve():
    for i in range(n-1,-1,-1):
        for j in range(i+1):
            if A[i] - A[j] in sample:
                return A[i]

print(solve())