Part6.4_완전탐색_깊이,넓이 우선탐색활용_동전바꿔주기(DFS)

내가 생각한 코드

import sys
sys.stdin = open("input.txt", "rt")

def DFS(L,sum):
    global cnt
    if sum == n:
        cnt += 1
        return
    if L == k:
        return
    if sum > n:
        return
    
    else:
        for i in range(0,R[L]+1):
            DFS(L+1, sum+(G[L]*i))
         
if __name__ == "__main__":
    n = int(input())
    k = int(input())
    cnt = 0
    G = []
    R = []

    for _ in range(k):
        a, b = map(int,input().split())
        G.append(a)
        R.append(b)
    DFS(0,0)
    print(cnt)

어휴 간만에 풀었다 ㅠㅠㅠ

선생님 코드

상태트리로 문제를 풀으셨다..

import sys
sys.stdin = open("input.txt", "rt")

def DFS(L,sum):
    global cnt
    if sum > T:
        return

    if L == k:
        if sum == T:
            cnt += 1
        
    else:
        for i in range(cn[L]+1):
            DFS(L+1, sum+(cv[L]*i))
           
if __name__ == "__main__":
    T = int(input())
    k = int(input())
    cv = list() # 동전 종류
    cn = list() # 동전 개수

    for _ in range(k):
        a, b = map(int,input().split())
        cv.append(a)
        cn.append(b)
    cnt = 0
    DFS(0, 0)
    print(cnt)