[완전탐색][트리] - 동전 분배하기(DFS)

문제

3명에게 n개의 동전을 나눠줄 때 제일 큰 금액을 가진자와 제일 작은 금액을 가진자의 차가 최소가 되게 하라

문제 풀이

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

            #해당 작업이 끝나고 다시 윗 노드로 온 상황이기에 해당 값을 빼주어야 한다.(안 그러면 누적되기 때문)
            abc[i] -= coin[L]


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

• 3명에게 동전을 나누기 위해서 for문을 3번 반복한다.
• 이때 핵심은 DFS 작업이 끝난 뒤 다시 윗 노드로 돌아가는 상황인데 이땐 더해줬던 값을 뺴주어야 다음 진행이 가능하다.
• 또한 세명의 총액이 달라야 하기에 자료구조 set을 사용해서 확인해준다.
  • 하나라도 같다면 len(tmp)는 3이 나오지 않는다.
  • 다 다르다면 len(tmp)는 3이 나온다.