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

코딩코딩코딩코님의 프로필 이미지

작성한 질문수

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

2. 네트워크 선 자르기(Top-Down : 재귀, 메모이제이션)

이 함수가 왜 돌지 않는지 모르겠습니다

작성

·

245

0

n = int(input())

def func(v):
    if v == 1:
        return 1
    if v == 2:
        return 2
    if dp[v] != 0:
        return dp[v]
    else:
        dp[v] = func(v-2) + func(v-1)
dp = [0] *(n+1)

func(n)
print(dp[n])

dp[v]!=0이 아니면 return dp[v]를 반환해주는 조건을 했는데
왜 오류가 뜨는지 모르겠습니다.
nontype 과 nontype은 더할 수 없다는데 디버깅을 해봐도 모르겠습니다 ㅠㅠ

답변 2

0

김태원님의 프로필 이미지
김태원
지식공유자

안녕하세요^^

n=5라고 할 때 func(5)가 최초로 호출되어 위에 코드를 돌린다면 func(3)이 func(1)이 반환해준 값과 func(2)가 반환해준 값을 받아 계산되듯이 func(3)도 자신의 값을 func(4)에게 반환해주어야 func(4)도 계산을 할 수 있습니다.

0

왜 else에 return dp[v]를 해줘야하는지 모르겠습니다