[백준] 2295 세 수의 합

문제 설명

a + b + c = d 가 모두 집합 U에 속할 때 d가 최대인 경우를 구하는 것이 문제이며 a,b,c,d는 서로 같을 수 있다.

쉽게 3중 for 문으로 해결할 수 있을 것 같다. 그럼 for 문의 들어갈 n의 조건을 확인해보자

안타깝게도 n이 1000까지 들어 올 수 있다. 이를 3중 for문으로 구현한다면 1000000000의 범위를 가지기 때문에 시간초과가 뜰 것이다. 이 범위를 어떻게 하면 줄일 수 있을까?

a + b + c = d에서 하나를 이항시켜 보자
=> a + b = d - c 의 경우 이중 for 문과 여기서 얻은 값을 한번 더 비교해서 2000000의 범위로 해결할 수 있을 것 같다.

이 아이디어로 문제를 해결 해 보자

코드 설명

n = int(input())

u = set()
for i in range(n):
    u.add(int(input()))

a_b_sums = set()
for i in u:
    for j in u:
        a_b_sums.add(i + j)

ans = {}
for i in u:
    for j in u:
        if (i - j) in a_b_sums:
            ans[i] = (i, j, i - j)

keys = list(ans.keys())
keys.sort(reverse=True)
print(keys[0])

u : 문제에서도 집합이라고 정의하였으니 set으로 만들어 준다.(중복을 허용하지 않음)
a_b_sums : 집합 u의 구성요소 중 두가지를 뽑아 조합할 수 있는 모든 합의 결과를 중복이 제거된 상태로 만들어 준다.
ans : d - c가 a + b와 같은 경우의 d 값을 key로가지는 딕셔너리
ans 의 key를 뽑아 리스트로 바꿔주고 내림차순으로 정렬 해주면 이 리스트의 0번째가 문제의 조건을 만족하는 답이 된다.

수정한다면

이 문제에서는 a, b, c에 대한 정보는 필요하지 않기 때문에 d에 대한 정보만을 얻고자 한다면 딕셔너리인 ans를 set으로 구성했다면 key 값을 따로 추출할 필요 없이 set을 list로 바꿔주고 정렬하는 과정만 거치면 답을 구할 수 있을 것으로 생각 됨