파이썬 알고리즘 059 | 동전 분배하기(DFS)**

59. 동전 분배하기(DFS)

N개의 동전을 A, B, C 세명에게 나누어 주려고 합니다.
세 명에게 동전을 적절히 나누어 주어, 세 명이 받은 각각의 총액을 계산해, 총액이 가장 큰
사람과 가장 작은 사람의 차가 최소가 되도록 해보세요.
단 세 사람의 총액은 서로 달라야 합니다.
▣ 입력설명
첫째 줄에는 동전의 개수 N(3<=N<=12)이 주어집니다.
그 다음 N줄에 걸쳐 각 동전의 금액이 주어집니다.
▣ 출력설명
총액이 가장 큰 사람과 가장 작은 사람의 최소차를 출력하세요.
▣ 입력예제 1
7
8
9
11
12
23
15
17
▣ 출력예제 1
5
해설 : 29(12+17), 32(8+9+15), 34(11+23) 로 분배하면 최대금액과 최소금액의 차가 5가 되어 5가 최
소차가 된다.

<내 풀이>

접근 방법을 생각하지 못하겠음 ㅠㅠ...상태트리를 구현하지 못하겠음

• 풀이를 듣고 구현했는데도 답이 나오지 않음
  ===>아...x가 t가 됐을 때 멈췄어야 하는데 k로 설정해두었었음..바보
  ===> +그리고 j안에 있는 세개의 값이 다 달라야 하므로 set을 이용해서 검사를 했어야 한다
  ===> 또 다시 back 할 때 j[i]에 있던 애를 전 상태로 되돌려놔주어야 한다

def dfs(x) : 
    if x==k:
        a=max(j)-min(j)
        if a<l:
            l=a  #===> money에 있는 금액 서로 다르다는 거 확인해야함
        return
    else :
        for i in range(3) :
            j[i]+=cost[x]
            dfs(x+1) 
            j[i]-=cost[x] 

if __name__=='__main__' :
    cost=[]
    t=int(input())
    for i in range(t) :
        k=int(input())
        cost.append(k)
    l=9999
    j=[0]*3
    dfs(0)
    print(l)
    

<풀이>

• coin(L)번째의 동전을 세명에게 나눠주는 경우 계속 존재
  (0,1,2)

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]

if __name__=="__main__":
    n=int(input())
    coin=[]
    tmp=[]
    money=[0]*3
    res=2147000000
    for _ in range(n):
        coin.append(int(input()))
    DFS(0)
    print(res)
    

<반성점>

• 상태트리를 생각해내지를 못한다
• 세명에게 나눠주는 각각의 경우만 구하면 되니깐 조금만 생각하면 됐을텐데 너무 졸린 상태에서 생각해서 생각에 도달하지 못한 것 같다
  앞으로는 좀 더 고민해보자

<배운 점>

• set을 써서 중복되는 것이 존재하는 지 확인하는 것, 조건을 꼼꼼히 체크해주기
• 특히 back 할 때 제거하는 거 여부를 잘 체크하기

<2회독 내 풀이>

def dfs(x) :
    global mini
    if x>n:
        return
    if x==n:
        if len(set(res))==3 and sum(res)==sum(aa):
            d=(max(res)-min(res))
            if d<mini:
                mini=d
    else :
        for i in range(3):
            res[i]+=aa[x]
            dfs(x+1)
            res[i]-=aa[x]
if __name__=='__main__' :
    mini=1000
    dd=[]
    aa=[]
    n=int(input())
    res=[0]*3
    for i in range(n) :
        a=int(input())
        aa.append(a)
    dfs(0)
print(mini)