동전 바꿔주기(DFS)

인프런 김태원님의 파이썬 알고리즘 문제풀이를 듣고 작성한 글입니다.

https://inf.run/P97f

파이썬 알고리즘 문제풀이 (코딩테스트 대비) - 인프런 | 강의

내 풀이 (정답 아님)

#내 풀이
def DFS(L, sum):
    global cnt
    if sum > T:
        return
    if sum == T:
        cnt += 1
        return
    if L == k:
        return
    else:
        for i in cn:
            for j in range(i+1):
                DFS(L+1, sum+cv[L])
                DFS(L+1, sum)

if __name__ == "__main__":
    cv = []
    cn = []
    T = int(input())
    k = int(input())
    for i in range(k):
        a, b = map(int, input().split())
        cv.append(a)
        cn.append(b)

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

대충 가닥은 생각해서 진행했는데

답이 예상대로 나오지 않았다.

---

강의 풀이

#강의 풀이
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 i in range(k):
        a, b = map(int, input().split())
        cv.append(a)
        cn.append(b)
    cnt = 0
    DFS(0, 0)
    print(cnt)

어디가 문제였냐면

동전의 개수만큼 반복해서 sum을 더하는 부분이 잘못되었다.

DFS를 동전의 개수만큼 재귀하는데

동전을 0개, 1개, 2개, ... 이런식으로 갈래를 나눠서

sum에 동전개수 i개를 곱해서 더해야한다.