return

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)

7. 동전 교환-Cut Edge Tech

작성

226

L은 dfs를 진행할수록 증가하기 때문에 만약 L에서 sum이 m인 부분을 찾았으면 더 진행할 필요없이 L이 최소라고 생각해서 dfs함수에서

    if L>=res:
        return

을 생략하고

def DFS(L, sum):
    global res
    
    if sum>m:
        return
    if sum==m:
        if L<res:
            res=L
            return #
    else:
        for i in range(n):
            DFS(L+1, sum+a[i])

sum이 m을 되자마자 return 하는게 나을거라 생각했는데 제 생각과는 달리 더 오래걸리더라구요. 왜 그런지 이유를 모르겠어요.

python 코테 준비 같이 해요!

답변 2

Jerry

위와 같을 경우 return이 아니라 아예 exit으로 종료시키면 되나요?

김태원

지식공유자

안녕하세요^^

exit는 답을 찾았을 때 답을 출력하고 프로그램을 종료하는 논리입니다. 이 문제는 exit를 쓰는 문제가 아니라 가지치기를 잘 해야하는 문제입니다. 그리고 어떤 회사는 테스트에서 exit를 막아놓는 회사도 있습니다.

김태원

지식공유자

안녕하세요^^

sum이 m이 되자마다 return 한다고 해서 호출되어 스택에 저장되어 있는 모든 함수가 종료되는 것은 아닙니다. 방금전 호출된 함수만 종료되는 것입니다.

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

return