Inflearn Community Q&A
asked
sum 계산시
Written on
·
265
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])가 아닌 위 하늘색 부분처럼 미리 계산해서 넘겨주면 결과가 다르게 나오던데 제 눈에는 같아 보여서요...! 결과가 달라지는 이유가 궁금합니다.
python코테 준비 같이 해요!
Answer 1
1
codingcamp
Instructor
안녕하세요^^
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]값을 빼주어야 합니다.