[인프런] 동전 분배하기

---

문제설명

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

입력조건

• 첫줄에는 동전의 개수 N(3 <= N <= 12)이 주어진다.
• 그 다음 N줄에 걸쳐 각 동전의 금액이 주어진다.

출력조건

• 총액이 가장 큰 사람과 가장 작은 사람의 최소차를 출력한다.

사고과정

• 상태트리를 적절히 잘 구현했다! 상태트리의 레벨은 동전의 인덱스를, 갈래길은 해당 동전을 A, B, C 각각 사람에게 나누어줄 경우로 뻗어 나가면 된다. 단, 주의할 점은 다시 백트레킹할 때는 백트레킹하기 전 더해주었던 동전을 다시 빼주어야 한다!
• 강의 속 풀이와 다른 점은 A, B, C 각 총액이 서로 달라야 한다는 조건 확인만 다르게 구현했다. 나는 하나의 if문으로 강의 속에서는 집합 자료구조를 활용해 구현했다.

풀이

- 나의 풀이

n = int(input())
coin = [int(input()) for _ in range(n)]
res = [0] * 3  # A, B, C 각 분배되는 동전
answer = 2174000000

def dfs(L):
    global answer
    if L == n:
        if res[0] != res[1] and res[1] != res[2] and res[0] != res[2]:
            answer = min(answer, max(res)-min(res))
        return
    else:
        for i in range(0, 3):  # A, B, C
            res[i] += coin[L]
            dfs(L+1)
            res[i] -= coin[L]

dfs(L=0)
print(answer)

- 강의 풀이

n = int(input())
coin = []
money = [0] * 3
res = 2147000000
for _ in range(n):
    coin.append(int(input()))


def DFS(L):
    global res
    if L == n:
        cha = max(money) - min(money)
        if cha < res:
            tmp = set()
            for x in money:
                tmp.add(x)
            if len(tmp) == 3:
                res = cha
    else:
        for i in range(3):
            money[i] += coin[L]
            DFS(L+1)
            money[i] -= coin[L]


DFS(0)
print(res)