dp

DP

• Dynamic Programing
• 이전의 값을 재활용하는 알고리즘
• 예시 : 1~10 숫자 중, 각각 이전 값들을 합한 값 구하기
• 이전의 값을 활용해서 시간복잡도 줄일 수 있음.
• 이전값 을 어떻게 구해야하는지에 대한 점화식이 필요.
• dp: 이전값 , 점화식: An = A(n-1) + A(n-2)
• 점화식 먼저 짜고 코드짜기, 어떻게 할지 모르겠을 땐, 하나씩 그려보면서 규칙찾기.

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

 

출력

- 첫째 줄에 2 x n 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

 

* 점화식만들기

n = 1 => 1

n = 2 => 2

n = 3 => 3 = 1+2

=> A(n) = A(n-1) + A(n-2)

 

*점화식을 이용해 DP 알고리즘 짜기

 

"""
* 아이디어
- A1:1, A2:2, A3:1+2
- 점화식 : An = A(n-1) + A(n-2)
- N값을 구하기위해 for문으로 3부터 N까지 돌면서 (n이 2일경우 A(n-2)는 0인데 해당값은 없기때문)
- 이전값과 그 이전 값을 더해서 저장(이때 10007로 나눈 나머지값)
  

* 시간복잡도
- for : N > O(N)

* 자료구조
- DP 저장하는 경우의 수 배열(An) : int[]
- 최대값 : 10006 > Int 가능
"""

import sys
input = sys.stdin.readline

n = int(input())
# 아무것도 없을때 0, 1칸일때 1, 2칸 2
rs = [0,1,2] 

for i in range(3, n+1):
	rs.append((rs[i-1] + rs[i-2])%10007)
    
print(rs[n])

 

 

출처_

https://www.youtube.com/watch?v=qLkFBk5-HrY&list=PLi-xJrVzQaxXC2Aausv_6mlOZZ2g2J6YB&index=9