백준 11727 - 2×n 타일링 2 (Python)

문제

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

풀이

n = int(input())

dp = [-1]*(n+1)

dp[0] = 1
dp[1] = 1

for i in range(2,n+1):
    dp[i] = 2 * dp[i-2] + dp[i-1]

print(dp[n]%10007)

 

이 문제에서 2×N을 채우는 경우의 수는 세가지로 나뉜다.

1) 2×(N-2)를 채우고 = 모양을 더하는 경우

2) 2×(N-2)를 채우고 ㅁ 모양을 더하는 경우

3) 2×(N-1)을 채운 뒤 l 모양을 더하는 경우

즉, 2×N을 채우는 경우의 수는 2×(N-2)를 채우는 경우의 2배에  2×(N-1)을 더한 값이다.

N=1일때 경우의 수는 1, N=2일때 경우의 수는 3이라는 것을 기본값으로 해서 동적계획법을 사용하여 N번째 값을 구하고 10007로 나누어서 출력해주었다.

 

이 문제는 11726번 문제와 비슷하며 해당 문제의 풀이는 아래를 참고하면 된다

https://jamie2779.tistory.com/38

백준 11726 - 2×n 타일링 (Python)