[자료구조] 동적계획법 Dynamic Programming / 파이썬 Python

동적계획법 (Dynamic Programming)

처음에 나온 해답을 통해서 그다음 문제의 해답을 구한다.

간단히 말해 '점화식'을 이용하여 문제를 풀어나감

 

메모이제이션을 하는 것 => 리스트에 저장

 

메모이제이션 X => 그저 재귀함수

 

예제 문제를 풀면서 감을 익혀나가는 것이 가장 중요.

 

예제문제 1. 네트워크 선 자르기

- 1m 선을 자를 때 경우의 수: 1가지

- 2m 선을 자를 때 경우의 수: 2가지

1 + 1

2

- 3m 선을 자를 때 경우의 수: 2 + 1 = 3가지

1) 마지막 선의 길이를 1m로 한다고 하자,

남은 선의 길이는 2m이다. 2m 선을 자르는 경우의 수는 2가지

2) 마지막 선의 길이를 2m로 한다고 하자,

남은 선의 길이는 1m이다. 1m 선을 자르는 경우의 수는 1가지

 

- 4m 선을 자를 때 경우의 수:

1) 마지막 선의 길이를 1m로 한다고 하자,

남은 선의 길이는 3m이다. 3m 선을 자르는 경우의 수는 3가지

2) 마지막 선의 길이를 2m로 한다고 하자,

남은 선의 길이는 2m이다. 2m 선을 자르는 경우의 수는 2가지

 

.

.

.

따라서 N번째 선을 자를 때 경우의 수는 N-1 번째 경우 + N-2 번째 경우이다.

 

 

풀이 1

n = int(input())

dy = [0]* (n+1) # 0을 포함하여 n개 => 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])

 

풀이 2 (DFS 이용)

def DFS(len):
    if dy[len]>0:
        return dy[len]
    if len==1 or len==2:
        return len
    else:
        dy[len]=DFS(len-1)+DFS(len-2)
        return dy[len]

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