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

💨 동적계획법이란? 네트워크 선 자르기(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)
dp[1] = 1
dp[2] = 2

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

print(dp[n])

⚽ 코멘트

문제에서 선을 1m,2m의 길이를 갖는 선으로 자르다고 한다.

• 자르는 위치에 따라서 방법이 다르다. 1 + 1 + 2 와 2 + 1 + 1은 다른 경우이다.

이 문제를 어떻게 접근해야 하나면... 예시처럼 7m를 한번에 계산할 수 없다는 생각은 할 수 있다.

문제에서 1m,2m의 길이를 갖는 선으로 자른다고 했으니 가장 작은 단위부터 생각해봐야 한다.

⚽ 1m의 경우 직관적으로 1m 1개로 1가지만 존재한다. 2m의 경우 역시 직관적으로 1m 2개, 2m 1개 경우만 존재한다. 즉 2가지가 존재한다.

• 이제 직관적인 부분은 dp에 채워놓고 시작할 수 있다. (dp로 풀 때 직관적으로 알 수 있는 것은 미리 초기화를 시켜놔야 한다.)

이제 3m부터는 더 작은 문제로부터 답을 도출할 수 있는지 확인해야 한다.

• 3m가 있다면.. 가장 마지막 토막이 1m or 2m로 나눠볼 수 있다.
• 즉 이 문제 점화식 세울 때 가장 마지막 토막이 1m or 2m인 경우로 나눠서 생각할 수 있다.

⚽ 점화식 접근할 때 마지막 부분을 통해 생각하는 습관을 기르자.

• 이 문제를 생각하면 마지막 부분을 2로 자를 때 1m 2개짜리로 자르는 것은 생각할 필요가 없다. 이유는 이미 앞에서 마지막 토막이 1인 경우를 생각했다 ! 그렇기에 생각 안해줘도 되는거지.