파이썬 알고리즘 072-2 | 네트워크 선 자르기(Top-Down : 재귀, 메모이제이션)

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

현수는 네트워크 선을 1m, 2m의 길이를 갖는 선으로 자르려고 합니다.
예를 들어 4m의 네트워크 선이 주어진다면
1) 1m+1m+1m+1m
2) 2m+1m+1m
3) 1m+2m+1m
4) 1m+1m+2m
5) 2m+2m
의 5가지 방법을 생각할 수 있습니다. (2)와 (3)과 (4)의 경우 왼쪽을 기준으로 자르는 위치가
다르면 다른 경우로 생각한다.
그렇다면 네트워크 선의 길이가 Nm라면 몇 가지의 자르는 방법을 생각할 수 있나요?
▣ 입력설명
첫째 줄은 네트워크 선의 총 길이인 자연수 N(3≤N≤45)이 주어집니다.
▣ 출력설명
첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.
▣ 입력예제 1
7
▣ 출력예제 1
21

<내 풀이>

메모이제이션에 대해서도 배웠음

<풀이>

(1) 메모이제이션만 하고 가지컷은 하지 않은 것

def dfs(len):
    if len==1 or len==2: #종착점
        return len
    else :
        dy[len] = dfs(len-1)+dfs(len-2) # dfs(7)=dfs(6)+dfs(5)
        return dy[len]

if __name__=='__main__':
    n=int(input())
    dy=[0]*(n+1)
    print(dfs(n))

(2) 이미 값이 정해진 애를 만나면 가지 cut해주기

def dfs(len):
    if dy[len]>0: #이미 입력돼있을 때! 밑으로 가지 뻗지 말고 원래 있던 값 return해라
        return dy[len]
    if len==1 or len==2: #종착점
        return len
    else :
        dy[len] = dfs(len-1)+dfs(len-2) # dfs(7)=dfs(6)+dfs(5)
        return dy[len]

if __name__=='__main__':
    n=int(input())
    dy=[0]*(n+1) #기록할 테이블
    print(dfs(n))

<반성점>

<배운 점>

• 메모이제이션 : 기록테이블에 값 구한 것을 저장해놓는 것