-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
동전교환 효율성
23.01.24 12:37 작성 23.01.24 12:38 수정 조회수 329
0
안녕하세요
동전교환문제에서 저는 부분집합을 만들고 계산은 마지막에 하는 방식으로 풀어봤습니다.
효율성 방식에서 상태트리로 쭉 나가는 강사님 방식이랑 비교하면 뭐가 더 나은가요?
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)
답변을 작성해보세요.
0
김태원
지식공유자2023.01.29
안녕하세요^^
영상의 방법처럼 sum값을 계속 구하면서 재귀를 돌리면 if(sum > m) 으로 컷 에지를 할 수 있습니다. 영상의 방법이 더 효율적입니다.
답변 1