[김태원 알고리즘] 동전 분배하기 (DFS)

사용 언어: Python3

문제

풀이

내 풀이 - 세 사람의 총 금액을 tot 리스트로 선언

import sys
sys.setrecursionlimit(10**6)

def DFS(L):
    global mn
    if L == N:
        if len(set(tot)) == 3:
            mn = min(mn, max(tot) - min(tot))
    else:
        for i in range(3): # A, B, C 각각이 가진 경우
            tot[i] += coin[L] 
            DFS(L+1)
            tot[i] -= coin[L] # ✅ back

N = int(input())
coin = [int(input()) for _ in range(N)]

tot = [0] * 3 # 3명의 총액
mn = 2147000000

DFS(0)
print(mn)

• 이 풀이가 아래 풀이보다 더 깔끔하고 좋은 것 같다! 👍

내 풀이 - 세 사람의 총 금액을 DFS의 매개변수로 전달

import sys
sys.setrecursionlimit(10**6)

def DFS(L, aSum, bSum, cSum):
    global mn
    if L == N:
        tmp = [aSum, bSum, cSum]
        if len(set(tmp)) == 3:
            mn = min(mn, max(tmp) - min(tmp))
    else:
        DFS(L+1, aSum + coin[L], bSum, cSum)
        DFS(L+1, aSum, bSum + coin[L], cSum)
        DFS(L+1, aSum, bSum, cSum + coin[L])

N = int(input())
coin = [int(input()) for _ in range(N)]

mn = 10000
DFS(0, 0, 0, 0)
print(mn)

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기