[인프런] 동전 분배하기

문제

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

입력

첫째줄에는 동전의 개수 N(3 <= N <= 12)가 주어진다.
그 다음에는 N줄에 걸쳐 각 동전의 금액이 주어진다.
e.g)
7
8
9
11
12
23
15
17

출력

총액이 가장 큰 사람과 가장 작은 사람의 최소차를 출력하라.
e.g)
5

생각

• 동전을 분배할 수 있는 많은 경우의 수 중 가장 최적의 조건을 탐색해야한다. 많은 경우의 수를 탐색해야하기 때문에 DFS를 활용하여 문제를 풀어야겠다.
• 주어진 동전으로 세명에게 분배해야하기 때문에 각 노드에서 셋으로 뻗어나가는 분기로 상태트리를 구성하자.
• 결괏값을 저장할 리스트를 생성하고, 해당 리스트의 각 index를 A,B,C라고 생각하여 깊이 탐색할 때 각 index에 동전의 값을 더해주도록 하자.
• 트리의 끝까지 탐색 후 백 트래킹을 할 땐, 더한 동전의 값을 다시 빼주고 다음 사람에게 더해줘야한다는 것을 주의하자.
• 마지막 출력값에서 중복이 있으면 안된다. 따라서 set() 자료구조를 사용하자.

Solution

n = int(input())
coins = [int(input()) for _ in range(n)]
ret = 2147000000
people = 3
money = [0] * people


def dfs(level):
    global ret

    if level == n:
        difference = max(money) - min(money)
        if difference < ret:
            tmp = set()
            for x in money:
                tmp.add(x)
            if len(tmp) == people:
                ret = difference
    else:
        for i in range(people):
            money[i] += coins[level]
            dfs(level+1)
            money[i] -= coins[level]


dfs(0)
print(ret)