소스코드

import sys
input = sys.stdin.readline

# arr[x] + arr[y] = arr[k] - arr[z] 를 만족하는 arr[k]의 최대값 구하기

N = int(input().rstrip())
arr = sorted([int(input().rstrip()) for _ in range(N)])
two_sum = set()
result = 0

for x in range(N):
    for y in range(N):
        two_sum.add(arr[x] + arr[y])

for k in range(N - 1, -1, -1):
    for z in range(k - 1, -1, -1):
        two_sub = arr[k] - arr[z]

        if two_sub in two_sum:
            result = max(result, arr[k])

print(result)

풀이

1. arr[x] + arr[y] + arr[z] = arr[k] 를 만족하는 arr[k]의 최대값을 찾는 문제이다. 이 때, x, y, z를 중복조합으로 뽑는 풀이는 O(N^3)로 TLE가 난다. 다행히 문제를 약간 변형하여 시간복잡도를 줄이는 방법이 있다.

2. arr[x] + arr[y] = arr[k] - arr[z] 로 식을 변형한다. 주어진 집합의 모든 수에 대해 2개의 쌍을 모두 구하여, 그 합을 two_num 집합에 넣어둔다. 이 때의 시간복잡도는 O(N^2) 이다.

3. 이제 비슷한 방식으로 모든 수의 2개의 쌍에 대하여 차를 계산하고, 그 것이 two_num에 존재하면 그 때의 k를 result에 최대를 갱신해나간다.

   이 때 주어진 집합의 원소는 모두 자연수이므로, 두 수의 합이 0 이하가 될 수 없으니 이를 고려하여 이중 for문을 작성했다.

   역시 이 때의 시간복잡도도 O(N^2) 이다.

어려웠던 점, 배운 점

• 중복조합 풀이밖에는 안 떠올라서 결국 다른 사람 풀이를 참고했다. 이런 야무진 아이디어는 도대체 어떻게들 생각해내시는건지.. 나도 이런 아이디어를 떠올릴 수 있을만큼 넓은 시야와 창의력을 가질 수 있게 더 노력해야겠다 ㅠ

• 다른 사람 풀이 중에는 투 포인터 변형 풀이도 있었다. 언뜻 보기에는 TLE가 날 것 같아 보였는데.. 암튼 신기했다.