백준 (boj) 파이썬 - 11726 번 : 2 x n 타일링 (DP)

문제 링크 : https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

 

 

 

---

 

 

문제 분류 : 다이나믹 프로그래밍 https://infinitt.tistory.com/246

알고리즘 - 다이나믹 프로그래밍 (Dynamic Programming)

 

 

생각보다 점화식이 빨리 찾아졌다. 문제의 의도는 타일의 구성을 통해 점화식을 찾으라는것 같은데 숫자를 보면 피보나치와 유사한 형태의 점화식이 세워진다.

입력 N	1	2	3	4	5	6
방법의 수	1	2	3	5	8	13

 

점화식 : dp[N] = dp[N-1]+dp[N-2]

 

 

 

 

 

 

*정답코드 (Python)

n = int(input())

dp = [0 for _ in range(n+1)]

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

	print(dp[i]%10007)