62)동전 분배하기(DFS)

문제

N개의 동전을 A, B, C 세명에게 나누어 주려고 합니다.

 

세 명에게 동전을 적절히 나누어 주어, 세 명이 받은 각각의 총액을 계산해, 총액이 가장 큰 사람과 가장 작은 사람의 차가 최소가 되도록 하기

 

조건

단 세 사람의 총액은 서로 달라야 합니다.

 

제한사항

첫째 줄에는 동전의 개수 N(3<=N<=12)이 주어집니다.

 

그 다음 N줄에 걸쳐 각 동전의 금액이 주어집니다.

 

총액이 가장 큰 사람과 가장 작은 사람의 최소차를 출력하세요.

 

문제풀이

def go(L):
  global res

  if L==N:
    diff=max(money)-min(money)
    if diff<res:
      tmp=set()
      for x in money:
        tmp.add(x)
      if len(tmp)==3:
        res=diff
  else:
    for i in range(3):
      money[i]+=coin[L]
      go(L+1)
      money[i]-=coin[L]

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