[백준] 11726번: 2×n 타일링/ 파이썬

문제 링크

---

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

11726번: 2×n 타일링

 

풀이 코드

---

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)

코드 해석

---

다이나믹 프로그래밍 (DP) 문제이다.

 

우선 규칙을 찾는다.

규칙은 n의 방법의 수는 n-1 + n-2 이다.

n-1은 세워져있는 타일 한개가 붙는 경우,

n-2는 타일 두개가 붙는 경우이다.

 

그 후 dp형식으로 문제를 해결한다.