[DP] - 네트워크 선 자르기

 

 네트워크 선 자르기

현수는 네트워크 선을 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

 

 

나의 코드 (Bottom-Up)

n=int(input())

dp=[0]*(n+1)
dp[1]=1
dp[2]=2
for i in range(3,n+1):
    dp[i]=dp[i-1]+dp[i-2]
print(dp[n])

 

나의 코드 (Top-down)

def DFS(L):
    if L==1 or L==2:
        return L
    else:
        return DFS(L-1)+DFS(L-2)
   
n=int(input())
print(DFS(n))

 

1m를 자르는 방법의 수는 [1]로 1가지

2m를 자르는 방법의 수는 [1,1] [2]로 2가지 로 직관적으로 알수 있다.

이후 3m 이후 부터는 점화식을 찾는다 ..!

 

 

위 그림과 같이  4m는 3m를 자르는 방법수와 2m를 자르는 방법수의 합이고

5m는 4m를 자르는 방법수와 3m를 자르는 방법수의 합이다.