[백준] 11726번: 2×n 타일링 (python)

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

---

전형적인 DP 문제로 규칙을 찾아가면 되는 문제

n이 1000이하 값으로 크지 않기 때문에 1부터 모두 구해나가면 된다

---

 

규칙을 간단히 설명하면,

n = 1일때는 아래 그림과 같이 채울 수 있습니다.

 

n = 2일때는 아래 그림과 같이 채울 수 있습니다.

 

n = 3인 경우부터 규칙이 발생합니다. n = 1인 경우 뒤에 1 x 2 블록 두개를 쌓은 경우와 n = 2인 경우 뒤에 2 x 1 블록 한개를 쌓은 경우가 됩니다.

 

동일한 규칙으로 n = 4인 경우에는 n = 2인 경우 뒤에 1 x 2 블록 두개를 쌓은 경우와 n = 3인 경우 뒤에 2 x 1 블록 한개를 쌓은 경우가 됩니다.

 

 

따라서 n = (n - 2) + (n - 1) 의 규칙을 가지게 됩니다.

 

n = int(input())

dp = [0] * 1001
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
    dp[i] = (dp[i - 1] + dp[i - 2]) % 10007
print(dp[n])