[김태원 알고리즘] 동전 바꿔주기 (DFS)

사용 언어: Python3

문제

풀이

import sys
sys.setrecursionlimit(10**6)

def DFS(L, pSum):
    global cnt
    if pSum > T: # ✅ cut edge
        return
    if L == k: # ✅ 카운트 조건 주의
        if pSum == T:
            cnt += 1 # 카운트
    else:
        for i in range(coin[L][1] + 1): # ✅ 특정 동전이 n개 있을 때, 해당 동전 0개 ~ n개 사용 가능
            DFS(L+1, pSum + coin[L][0] * i)

T = int(input())
k = int(input())
coin = [tuple(map(int, input().split())) for _ in range(k)]

cnt = 0
DFS(0, 0)
print(cnt)

---

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

맨 위로 이동하기