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.txt", "r")
def DFS(L):
    global res
    if L == n:
      gap = max(money)-min(money)
      if gap < res:
         tmp = set()
         for x in money:
            tmp.add(x)
            if len(tmp) == 3:
                  res = gap
         

    else:
      for i in range(0, 3):
           money[i] = money[i] + coin[L]
           DFS(L+1)
           money[i] = money[i] - coin[L]

         
if __name__=="__main__":
  n=int(input())
  money=[0]*3  
  coin=[]
  res=2147000000
  for i in range(n):
    a = int(input())
    coin.append(a)
  DFS(0)
  print(res)

 

Hint

▶ 3개의 값이 모두 같이 않은 경우를 도출하는 방법

      1. tmp라는 임시 set을 만든다.

      2. 만약에 tmp에 3개의 값을 저장한다.

      3. set 특성상 set은 순서가 없으며, 중복을 허용하지 않는다.

      4. 따라서 3개의 값이 모두 다르다면, set의 길이는 3이어야 한다.

 

▶ 아래와 같이 코드를 짜는 경우에는 DFS(L+1, sum +α)를 하지 않아도,

    해당 인덱스에 값을 누적할 수 있다. 

   for i in range(0, 3):
           money[i] = money[i] + coin[L]
           DFS(L+1)
           money[i] = money[i] - coin[L]