[파이썬 알고리즘 문제풀이] - Section7 / 깊이/넓이 우선 탐색(DFS, BFS ) 활용 - 5

동전 분배하기(DFS)

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

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

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

▣ 입력예제 1
7
8
9
11
12
23
15
17

▣ 출력예제 1
5

import sys
# sys.stdin = open("input.text", "rt")
sys.setrecursionlimit(10000)


n = int(input())

data = []
for _ in range(n):
    data.append(int(input()))


res = 2424242424
def DFS(L, sumA, sumB, sumC):
    global res
    if L == n: #전부 다 확인. 종료조건
        if sumA == sumB or sumB == sumC or sumA == sumC: #이 조건 뺴먹음.
            return
        if sumA != sumB and sumB != sumC:
            a = max(sumA, sumB, sumC)
            b = min(sumA, sumB, sumC)
            if res > a - b:
                res = a-b
            
    else:
        DFS(L+1, sumA + data[L], sumB, sumC)
        DFS(L+1, sumA, sumB + data[L], sumC)
        DFS(L+1, sumA, sumB, sumC + data[L])
DFS(0,0,0,0)
print(res)

코멘트

DFS 문제는 상태트리만 시각화할 수 있다면 코드 구현은 매우 쉬워 !
이 문제 역시 A,B,C 세 명한테 각 동전을 주는 것인데 각 동전 별로 3가지 상태트리로 뻗어나가잖아 !!
그렇기에 모든 동전을 그렇게 상태트리를 뻗어나가면 끝 !

백트랙킹할 때 이전에 줬던 금액 빼줘야지. 근데 매개변수로 주면 굳이 안그래도 됨 (알아서 반영 되잖아)

만약 따로 리스트를 만들 것이라면.

def DFS(L):
    global res
    if L == N:  #인덱스 모두 돌았어. 종료조건
        cha = max(money) - min(money)
        if cha < res: 
            temp = set()   #중복이 있는지 확인하기 위해.
            for x in money:
                temp.add(x)  
            if len(temp) == 3:  #합이 모두 다를 때만!!!
                res = cha

    else:  #이제 가지가 뻗어나가야해.  세 가지! 각 동전이 세 사람한테 가야하니깐
        for i in range(3):
            money[i] += data[L] #i번째 사람에게 현재 동전을 줄꺼라서 
            DFS(L+1)  #그러고 다음 동전으로
            money[i] -= data[L]  #다시 함수가 끝나고 back했을 경우 다시 빼줘야지!!

money 리스트 따로 설정한다면 DFS해준 후 백 해서 돌아올 때 money[i]에 들어 있는 값을 다시 빼줘야 한다.
위 코드는 동일한 값을 set을 통해 처리해줌