DFS연습 - 동전 분배

연습을 안하면 또 까먹고 막막해질까봐 매일 DFS 연습을 해야지 싶다!

손으로 계획  -> 코드쓰기 -> 생각대로 안 되면 디버깅 이 순서대로 반복 공부중인데,

내가 어디서 실수하거나 놓치는지를 발견하게 되어서 아주 뿌듯하다.

 

📝 이번에 발견한 놓침 포인트

 ✔︎ 해당 턴에서 빠져나오면서 다시 자기 턴이 했던 작업을 초기화시켜야 하는 점

     (예를 들어 8원을 A에게 주는 작업을 하고 다시 빠져나올 때는 줬던 8원을 다시 뺏어와야 한다.)

 

❓ 궁금한 점

✔︎ 나는 이 문제에서 모든 경우를 다 돌고 있는데, 적절히 컷해서 백트래킹할 수 있는 방법은 없을까?

 

0. 문제

오늘의 문제는 A, B, C  3명에게 N개의 동전을 나누어주는 문제이다.

받은 동전의 총액이 가장 큰 사람과 가장 작은 사람의 차가 최소가 되도록 하고, 그 때의 최소차를 출력해야 한다.

단, 세 사람의 총액은 서로 달라야 한다.

 

1. 손정리

2. 코드

coins = [8, 9, 11, 12, 23, 15, 17]

each_sum = [0] * 3

minimum = 2147000000
def DFS(L):
    global minimum
    global each_sum
    if L == len(coins):
        isValid = True
        for each in each_sum:  # 세 사람이 가진 총액은 서로 달라야 한다는 조건을 충족시키기 위한 검사
            if each_sum.count(each) > 1:
                isValid = False
        if isValid:
            diff = max(each_sum) - min(each_sum)
            if diff < minimum:
                minimum = diff
        return

    else:
        for i in range(3):
            each_sum[i] += coins[L]
            DFS(L + 1)
            each_sum[i] -= coins[L]
            # 이게 내가 자주 계획단계에서 놓치는 것! 재귀에서 빠져나올 때는 내가 방금 칸에 더했던 것을 다시 빼줘야 한다.

DFS(0)
print(minimum)