파이썬 알고리즘-58 (DFS/BFS 활용) 동전 분배하기

58.동전 분배하기(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가 최소차가 된다.

내 코드

def dfs(v,suma,sumb,sumc):
    global difference
    if v==n:
        if suma==sumb or sumb==sumc or suma==sumc:
            return
        else:
            if max(suma,sumb,sumc)-min(suma,sumb,sumc)<difference:
                difference=max(suma,sumb,sumc)-min(suma,sumb,sumc)
    else:
        dfs(v+1,suma+lst[v],sumb,sumc)
        dfs(v+1,suma,sumb+lst[v],sumc)
        dfs(v+1,suma,sumb,sumc+lst[v])

n=int(input())
lst=[int(input()) for i in range(n)]
difference=int(1e10)
dfs(0,0,0,0)
print(difference)

동전의 개수만큼 재귀함수를 실행하면서, A,B,C에게 나누어주는 모든 방법의 수를 구했다. 시간초과가 나왔지만 컴퓨터 성능으로 인한 것일 뿐 논리에는 문제가 없는 것으로 보인다.

풀이

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)

반성점

• 서로 다른 n개가 있는지 찾을 때 set와 그것의 길이를 구하면 쉽게 찾을 수 있다.

배운 것