[김태원 알고리즘] 동전교환 (DFS)

사용 언어: Python3

문제

풀이

내 풀이

def DFS(L, pSum): # L: Level(=사용한 동전 수), partialSum: 사용한 동전의 합
    global mn
    if L >= mn:
        return # ✅ edge cut # 🌟 시간초과를 방지하는 중요한 코드이다!
    if pSum > M:
        return # ✅ edge cut
    if pSum == M:
        mn = min(mn, L)
    else:
        for x in lst:
            DFS(L+1, pSum+x)

N = int(input())
lst = list(map(int, input().split()))
M = int(input())

lst.sort(reverse=True)

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

• 정답 풀이와 같다😀

---

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

맨 위로 이동하기