인프런 커뮤니티 질문&답변
작성한 질문수
sum 계산시
작성
·
272
0
def DFS(L, sum):
global res
if L > res: ## Cut Edge
return
if sum > m:
return
if sum == m:
if L < res:
res = L
else:
for i in range(n):
sum += a[i]
DFS(L+1, sum)
안녕하세요! 문제 풀다가 궁금한 점이 생겨 질문드립니다.
sum을 넘겨줄때 DFS(L+1, sum + a[i])가 아닌 위 하늘색 부분처럼 미리 계산해서 넘겨주면 결과가 다르게 나오던데 제 눈에는 같아 보여서요...! 결과가 달라지는 이유가 궁금합니다.
퀴즈
재귀 함수에서 print 문을 재귀 호출 뒤에 두면 출력이 역순으로 되는 이유가 무엇일까요?
전역 변수 충돌 때문에
종료 조건이 없어서
스택에 쌓였다가 역순으로 처리돼서
지역 변수 우선순위 때문에
답변 1
1
안녕하세요^^
for i in range(n):
sum += a[i]
DFS(L+1, sum)
위와 같이 재귀를 호출하기 전에 sum에 미리 더해주면 백을 해서 되돌아 왔을 때 원래 sum값으로 되돌아와 다른 경우를 해야 하는데 sum에 a[i]가 더해진 값으로 되돌아 옵니다. 그래서
for i in range(n):
sum += a[i]
DFS(L+1, sum)
sum -= a[i]
처럼 재귀호출 아래에서 sum에서 a[i]값을 빼주어야 합니다.