[파이썬 알고리즘 문제풀이] - Section8 / Dynamic programming(동적계획법) - 2

💨 동적계획법이란? 네트워크 선 자르기(Bottom-Up)

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

의 5가지 방법을 생각할 수 있습니다. (2)와 (3)과 (4)의 경우 왼쪽을 기준으로 자르는 위치가 다르면 다른 경우로 생각한다.
그렇다면 네트워크 선의 길이가 Nm라면 몇 가지의 자르는 방법을 생각할 수 있나요?

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

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

▣ 입력예제 1
7

▣ 출력예제 1
21

import sys
sys.stdin = open("input.text", "rt")
input = sys.stdin.readline


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

def DFS(len):
    if dp[len] > 0:
        return dp[len]
    if len == 1 or len == 2: #종료조건
        return len
    else:
        dp[len] = DFS(len-1) + DFS(len-2)
        return dp[len]

print(DFS(n))

코멘트

이번에는 해당 문제를 탑다운 다이나믹 프로그래밍 방식으로 풀었다.
종료조건과 점화식을 작성하고, 가지 컷 해주면 돼