[알고리즘][Python] 백준(BOJ) 11727 2xn 타일링 2_파이썬

DP

11727 2xn 타일링 2    www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

 

 

 

 

문제 풀기 전 공부할 것 : 다이나믹 프로그래밍(DP)

 

 

 

 

 

 

 

풀이 1

<내용>

• 2 x n번째 직사각형을 타일로 어떻게 채울 수 있는가를 고민해야 한다.
• 먼저 2 x 1의 경우 2 x 1의 경우 1가지이다.
• 2 x 2의 경우 2 x 1을 2개 붙이는 경우, 1 x 2를 2개 붙이는 경우, 2 x 2 1개로 3가지이다.
• 2 x 3의 경우 2 x 2에 (2 x 1을 붙이는 경우) + 2 x 1에 (1 x 2를 2개 붙이는 경우 + 2 x 2를 1개 붙이는 경우)로 3(2 x 2에 2 x 1을 붙이는 경우) + 1(2 x 1에) X 2(1 + 1) = 5가지이다.
• 이와 같은 논리로 2 x n = (2 X (n-1)의 경우의 수) + (2 X (n-2)의 경우의 수 X 2) 식을 발견할 수 있다.
• 위의 식을 출력하는 코드를 작성하면 된다.
• 이때, 방법의 수를 10,007로 나눈 나머지를 출력하는 조건을 잊으면 안 된다.

 

 

 

<코드>

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