재귀함수가 많을 수록 안좋은건가요?

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

작성한 질문수

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

2. 휴가(DFS)

작성

275

import sys

#sys.stdin=open("input.txt", "rt")

def DFS(L,sum1,sum2):

global res

if sum1==0 and sum2==a[0]:

print(res)

sys.exit(0)

if L==n:

c=total-sum1-sum2

if sum1==sum2 or sum1==c or sum2==c:

return

ma=max(c,sum1,sum2)

mi=min(c,sum1,sum2)

if res>ma-mi:

res=ma-mi

else:

DFS(L+1,sum1+a[L],sum2)

DFS(L+1,sum1,sum2+a[L])

DFS(L+1,sum1,sum2)

if __name__=="__main__":

n=int(input())

a=list()

for i in range(n):

a.append(int(input()))

res=21470000

total=sum(a)

DFS(0,0,0)

이렇게 풀어서 1초에 다 맞추긴 했는데 강의와 많이 차이가나서 우울해야할지 좋아해야할지 모르겠습니다.

답변 1

지식공유자

코드를 보니 강의에서 설명한 것과 같은 논리입니다. 재귀함수도 저는 for문으로 세번 호출한 것이지 수진안님과 동일 코드나 다름없습니다. 우울해야 할 이유가 없어 보입니다. 스스로 이렇게 짠다는게 실력이 많이 올라가는 중인 것 같습니다.

추신) 동전분배 문제는 동전분배 영상에도 질문을 올리셔야 헷갈리지 않습니다. 아니면 제목에 문제이름을 넣어서 질문해주시면 감사하겠습니다.

작성한 질문수