[백준] 11727번(2xn 타일링 2) with Python

문제

www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

풀이

dp문제는 처음 풀어봐서 하나하나 그려서 규칙을 찾은 후 점화식을 구했다.

그림을 잘 못그려서 지저분함

위의 그림과 같이 N이 3 이상 이면

N-1에서 2x1 타일이 붙고, N-2에서 1x2 타일 두 개, 2x2 타일이 한 개 붙는 규칙이 계속된다. 

따라서, dp[n] = dp[n - 1] + dp[n - 2] * 2

dp[1]과 dp[2]를 미리 구해서 시작.

답

a = int(input())
dp = [0,1,3]
for i in range(3, a + 1) :
  dp.append(dp[i - 1] + dp[i - 2] * 2)
print(dp[a] % 10007)