파이썬 알고리즘-72 (DP) 네트워크 선 자르기

72.동적계획법이란? 네트워크 선 자르기(Bottom-Up)
현수는 네트워크 선을 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

내 코드

def dfs(v):
    global cnt
    if v==0:
        cnt+=1
    else:
        if v==1:
            dfs(v-1)
        else:
            dfs(v-2)
            dfs(v-1)

n=int(input())
cnt=0
dfs(n)
print(cnt)

DFS로 풀어봤지만 역시나 n이 커지면 기하급수적으로 실행시간이 늘어나 실패했다.

풀이

n=int(input())
dy=[0]*(n+1)
dy[1]=1
dy[2]=2
for i in range(3, n+1):
    dy[i]=dy[i-1]+dy[i-2]

print(dy[n])

DP를 쓰면 더 짧은 코드로 더 빠른 시간 안에 답을 구할 수 있다.

반성점

• 머리가 나쁘면 몸이 고생한다.

배운 것

• 동적 프로그래밍(DP): 전체적인 문제만 보면 해결하기 어려운 큰 문제이지만, 이를 아주 작게 쪼개서 직관적으로 봤을 때 해결할 수 있는 문제로 만든다. 여기서 구한 답을 바탕으로 조금 더 큰 문제를 해결해 나가면서 규칙을 발견하면 이를 점화식으로 작성하면 코드 구현은 어렵지않다. 그런데 규칙 발견하고 점화식 만드는게 가장 어려운 일이다.