[알고리즘]동전 분배하기

문제

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

▣ 입력설명
첫째 줄에는 동전의 개수 N(3<=N<=12)이 주어집니다. 그 다음 N줄에 걸쳐 각 동전의 금액이 주어집니다.

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

입력예제1

7
8
9
11
12
23
15
17

출력예제1

5

[내 코드]

def DFS(L,a_sum,b_sum,c_sum):
    global min_coin
    if N==L:
        if a_sum!=b_sum and b_sum!=c_sum and a_sum!=c_sum:
            k=max(a_sum,b_sum,c_sum)-min(a_sum,b_sum,c_sum)
            if k<min_coin:
                min_coin=k
            
        
    else:
        DFS(L+1,a_sum+a[L],b_sum,c_sum)
        DFS(L+1,a_sum,b_sum+a[L],c_sum)
        DFS(L+1,a_sum,b_sum,c_sum+a[L])
        



if __name__=="__main__":
    N=int(input())
    a=[]
    for _ in range(N):
        a.append(int(input()))
    
    min_coin=217400000
    DFS(0,0,0,0)
    print(min_coin)

1. 동전을 나누어 받는 A,B,C의 동전의 합계를 DFS함수 내에서 구현
2. 각각의 동전의 합계가 서로 달라야 하므로 가지치기
3. DFS를 3개의 노드로 각각 뻗어간다.

   A에게 동전을 분배(이 때, 동전은 a[L])
   B에게 동전을 분배(이 때, 동전은 a[L])
   C에게 동전을 분배(이 때, 동전은 a[L])

[해설코드]

def DFS(L):
	global cnt
    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]
if __name__=="__main__":
	n=int(input())
    coin=[]
    money=[0]*3
    res=2147000000
    for _ in range(n):
    	coin.append(int(input())
    DFS(0)
    print(res)
        

1.money배열에 나누어 가진 동전의 수 A,B,C를 기록한다.
2. money[i]-=coin[L] 이전의 노드로 돌아갈 때는 coin[L]값을 뺴준다.