[파이썬] [DP] 예제1 현수의 네트워크

동적계획법이란?

여러개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 확장하면서 주어진 문제를 해결하는 알고리즘

하위 문제를 풀고 그 값을 이용해 다음 문제를 풀고 그 결과를 이용해 또 다음 문제를 푼다.
f(n) = f(n-2)+f(n-1) 또는 f(n)=2*f(n-1) 같이

 

DP를 푸는 과정

1. 테이블 정의하기
2. 점화식 찾기
3. 초기값 정하기

문제

현수는 네트워크 선을 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 방식
f(n) = f(n-2)+f(n-1)

 

1m 네트워크선이 주어졌을 때, 1m 또는 2m로 자를 수 있는 경우의 수 1 

2m 네트워크선이 주어졌을 때, 1m 또는 2m로 자를 수 있는 경우의 수 2 

 - (1+1), (2) 

3m 네트워크선이 주어졌을 때, 1m 또는 2m로 자를 수있는 경우의 수 3 

 - (1+1+1), (1+2), (2+1)   

dy[1]=1 ==> 1미터를 자르는 방법은 1가지
dy[2]=2 ==> 2미터를 1미터씩 두개와 2미터로 한개 사용하는 방법 2가지
dy[3]=3 ==> 1미터씩 다루는 방법 1 + 2미터씩 다루는 방법 2 ==> 3

---

정답

 

Bottom-Up 방식

 

import sys

sys.stdin=open('input.txt','r')

if __name__=="__main__":
    n=int(input())
    dy=[0]*(n+1)                # 저장해 놓을 테이블을 정의한다
    dy[1]=1                     # 종이에 끄적이면서 점화식을 세운다.
    dy[2]=2                     # 규칙을 찾고 3번째 부터 적용되는 

    for i in range(3,n+1):
        dy[i]=dy[i-1]+dy[i-2]   # 점화식을 세운다.

    print(dy[n])

 

---

Top-Down 방식, 재귀

 

import sys

sys.stdin=open('input.txt','r')

def DFS(L):
    if dy[L]>0:            
        return dy[L]        
    if L==1 or L==2:        # 1이 되었을때 한가지, 2가 되었을때 두가지 출력하면 된다.
        return L 
    else:
        dy[L]=DFS(L-1)+DFS(L-2)
        return dy[L]
    

if __name__=="__main__":
    n=int(input())
    dy=[0]*(n+1)
    print(DFS(n))