인프런 커뮤니티 질문&답변

안녕하세요

동전교환문제에서 저는 부분집합을 만들고 계산은 마지막에 하는 방식으로 풀어봤습니다.

효율성 방식에서 상태트리로 쭉 나가는 강사님 방식이랑 비교하면 뭐가 더 나은가요?

def DFS(L):
    money= m
    global minn
    cnt=0
    if L==n: #계산은 여기서
        for i in range(0,n):
            if ch[i]==1:
                cnt+=(money//p[i])
                money%=p[i]
        if cnt<minn and money==0:
            minn=cnt
        
    else: # 깊이탐색해서 경우의 수 만들기
        ch[L]=0
        DFS(L+1)
        ch[L]=1
        DFS(L+1)