[Algorithms] 깊이/넓이 우선 탐색 (DFS, BFS) 활용-동전 바꿔주기(DFS)

 

• 출처가 올림피아드라고 해서 긴장했는데 다행히 맞추었다, 유후~!
• 1원짜리 동전을 0개 쓰는 경우, 1개 쓰는 경우, 2개 쓰는 경우 / 10원짜리 동전을 0개 쓰는 경우, 1개 쓰는 경우... 5개 쓰는 경우 .. 이런식으로 각 동전 타입에 대해 몇 개를 쓸 것인지 가짓수를 뻗어나가면 된다는 것이다 

 

def DFS(level, sum):
    global cnt
 
    if sum > target:
        return
 
    if level == types:
        if sum == target:
            cnt+=1
    else:
        for i in range(0, nums[level]+1):
            DFS(level+1, sum + (coins[level]*i))
 
 
if __name__ == '__main__':
    target = int(input())
    types = int(input())
    coins = []
    nums = []
    cnt = 0
 
    for _ in range(types):
        coin, num = map(int, input().split())
        coins.append(coin)
        nums.append(num)
 
    DFS(0, 0)
    print(cnt)