[Algorithm] 동전 분배하기 (DFS)

주어진 동전을 A, B, C 세 사람에게 나누는 것.
몇 개씩 나눌지는 정해지지 않았기 때문에 D() 안에는 동전 금액이 들어가야 하고 가지치기를 사람 수 만큼 가지를 쳐야 한다.

만약 3개씩 나눈다! 라고 정해졌다면 D(0)~D(2)까지로 D() 안에 동전 금액이 아닌 3개를 나타내는 수가 들어갔을 것이다.

def dfs(L):
    global m
    if L == n:
        if (max(money) - min(money)) < m:
            tmp = set()
            for x in money:
                tmp.add(x)
            if len(tmp) == 3:
                m = max(money) - min(money)

    else:
        for i in range(3):
            money[i] += graph[L]
            dfs(L+1)
            money[i] -= graph[L]


n = int(input())
graph = []
for _ in range(n):
    graph.append(int(input()))
money = [0, 0, 0]  # A, B, C
m = 2147000000
dfs(0)
print(m)