[인프런] 동전 분배하기

DFS 알고리즘
=> 상태트리 그리기!
경우에 따라 가지를 나눠주면 됨

문제

N개의 동전을 A, B, C 세명에게 나누어 주려고 합니다.
세 명에게 동전을 적절히 나누어 주어, 세 명이 받은 각각의 총액을 계산해, 총액이 가장 큰
사람과 가장 작은 사람의 차가 최소가 되도록 해보세요.
단 세 사람의 총액은 서로 달라야 합니다.

해설

동전 x를 3명 중 한 명에게 나눠줘야함
A에게 나눠주는 경우
B에게 나눠주는 경우
C에게 나눠주는 경우

총 3가지의 경우가 생김(가지 3개)

리스트를 만들어서 각각 사람에 대한 총합계를 누적
동전을 더한 다음에는 Back 할 것을 고려해 해당 동전을 다시 빼줌

# 7-5. 동전 분배하기(DFS)

# dfs는 상태트리 그리기!!
# 3명에게 나눠줌 -> 가지 3개 (경우의 수 3개)

def dfs(l):
    global res
    if l == n:   # 종료 조건
        if len(set(wallet)) != 3:  # 총액이 달라야함
            return
        else:
            # if (max(wallet) - min(wallet)) < res:  # 최소
            #     res = (max(wallet) - min(wallet))
            temp.append(max(wallet) - min(wallet))
    else:
        for i in range(3):  # 가지 3개
            wallet[i] += money[l]
            dfs(l+1)
            wallet[i] -= money[l]   # back 했을 때는 더해준거 빼야함


n = int(input())
money = []
for _ in range(n):
    money.append(int(input()))
wallet = [0, 0, 0]
temp = []
res = 2147000000

dfs(0)
print(min(temp))
# print(res)