-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
커팅조건
21.07.05 18:20 작성 조회수 188
0
import sys
import itertools as it
# sys.stdin = open("input.text", "rt")
input = sys.stdin.readline
n = int(input())
a = [int(input()) for _ in range(n)]
s = sum(a)
res = [0]*3
smallest = float('inf')
def dfs(l):
global smallest
if max(res)-s/3 > smallest:
return
if l == n:
tempSet = set(res)
tempList = list(tempSet)
if len(tempList) == 3:
smallest = min(smallest, max(res)-min(res))
else:
for i in range(3):
res[i] += a[l]
dfs(l+1)
res[i] -= a[l]
dfs(0)
print(smallest)
dfs 함수에 커팅 조건을 추가해주었는데 시간초과없이 통과가 되었습니다. 혹시 이 부분이 다른 데이터에서도 문제가 되지 않고 통과가 가능할까요 ? (반례가 존재하나요 ?)
답변을 작성해보세요.
0
답변 1