Algorithm - 동전 분배하기(DFS)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[동전 분배하기(DFS)]

 

N개의 동전을 A, B, C 세명에게 나누어 주려고 한다. 세 명에게 동전을 적절히 나누어 주어, 세 명이 받은 각각의 총액을 계산한 후 총액이 가장 큰 사람과 가장 작은 사람의 차가 최소가 되도록 만들고자 한다.

(단, 세 사람의 총액은 서로 달라야 함)

 

위의 조건을 모두 만족하는 프로그램을 작성하시오.

 

 

*입력 설명

첫 번째 줄에는 동전의 개수 N(3 ≤ N ≤ 12)이 주어진다.

그 다음 줄부터 각 동전의 금액이 주어진다.

 

*출력 설명

총액이 가장 큰 사람과 가장 작은 사람의 최소차를 출력한다.

 

 

---

 

 

풀이(Python)

답안

import sys
sys.stdin = open('AA/input_60.txt', 'rt')

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 = []
    money = [0] * 3
    res = 2147000000
    for _ in range(n):
        coin.append(int(input()))
    DFS(0)
    print(res)
    
# 출력 : 5

 

input_60.txt(입력)

7
8
9
11
12
23
15
17

 

 

중요내용

1. 변수 coin은 각 동전을 저장하는 리스트로 사용된다.
2. 변수 money는 세 명에게 분배되는 동전의 총 금액을 저장하는 리스트이다.
3. 변수 res는 금액 간의 최소차를 찾기 위해 사용된다.
4. DFS() 함수의 인자 L은 상태트리의 레벨이자 동시에 각 동전에 접근하는 리스트의 인덱스 번호로 사용된다.
5. 변수 money에 존재하는 동전의 총 금액이 중복되면 안되기 때문에, set 자료형을 활용하는 것이다.
6. 상태트리의 노드에서 나오는 가지는 세 명 중에게 동전을 분배하는 역할을 한다. (DFS 문제는 반드시 상태트리 활용)