[인프런] 네트워크 선 자르기(다이나믹 프로그래밍)

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

 

 

이제 드디어... 다이나믹 프로그래밍 제일 쉬운 문제가 이해가 되었다 ㅠㅠ

인프런 코테 강의는 너무 사랑이다...... 문제가 더 많으면 좋겠다.....

코테 처음 하시는 분을은 꼭 이거 들으세요

파이썬 알고리즘 문제풀이 (코딩테스트 대비) - 인프런 | 강의 (inflearn.com)

파이썬 알고리즘 문제풀이 (코딩테스트 대비) - 인프런 | 강의

 

bottom-up 방식

bottom-up 방식

n = int(input())

dy = [0] * (n + 1)      #n+1을 하는 이유는 1부터 사용하기 위함
dy[1] = 1               #초기 기본값
dy[2] = 2

#3부터 n+1까지
for i in range(3, n+1) :
    dy[i] = dy[i-1] + dy[i-2]

print(dy[n])

 

top-down 방식

작업하면서 만들어뒀던 값을 재활용한다!

dy = [0, 0, 0, 0, 0, 0, 0] 값을 저장해둔 다음에

dy[찾을길이]가 0이 아닌 경우에 dy값을 참조해준다.

 

#len은 구해야하는 길이가 되지만, dy의 인덱스이기도 함
def DFS(len) :
    #dy[len]이 0보다 크다면 dp를 통해서 값을 만들어둔 것이므로 참조함
    if dy[len] > 0 :
        return dy[len]
    #디폴트값
    if len == 1 or len == 2 :
        return len
    #dy = dy[len-1] + dy[len-2]
    else :
        dy[len] = DFS(len-1) + DFS(len-2)
        return dy[len]

n = int(input())
dy = [0] * (n + 1)

#top-down 방식으로 시작
print(DFS(7))