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

문제

네트워크 선의 길이가 Nm라면 몇 가지의 자르는 방법이 나오지는지 구하기

 

조건

현수는 네트워크 선을 1m, 2m의 길이를 갖는 선으로 자르려고 합니다.

 

예를 들어 4m의 네트워크 선이 주어진다면

의 5가지 방법을 생각할 수 있습니다.

 

(2)와 (3)과 (4)의 경우 왼쪽을 기준으로 자르는 위치가 다르면 다른 경우로 생각한다.

 

제한사항

첫째 줄은 네트워크 선의 총 길이인 자연수 N(3≤N≤45)이 주어집니다.

 

첫 번째 줄에 부분증가수열의 최대 길이를 출력한다.

 

문제풀이

def go(len):
  if dy[len]>0:
    return dy[len]

  if len==1 or len==2:
    return len

  else:
    dy[len]=go(len-1)+go(len-2)
    return dy[len]

N=int(input())
dy=[0]*(N+1)
dy[1]=1
dy[2]=2
print(go(N))