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

문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

 

기록

(dp 4일차) 저번에 풀었던 타일링 문제와 비슷했다. 달라진 점은 2x2타일이 추가되었다는 점.

>> 2021.07.23 - [알고리즘] - [백준 11726번] 2xn 타일링 (python)

 

문제는 각 2xn을 타일로 채우는 방법 수를 dp배열에 저장하여, dp[n]=dp[n-1](세로블럭 추가)+dp[n-2]*2(가로블럭2개 추가 or 2x2블럭 추가)의 점화식을 세워 계산하면 된다.

 

코드

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

1. 2xn을 타일로 채우는 방법 수를 저장할 dp 배열을 생성하여 0, 1, 2일 때를 초기화한다.

2. 3부터 n+1까지 dp[i-1]+dp[i-2]*2 의 점화식으로 계산한 방법 수를 저장한다.

3. 2xn에서의 방법 수를 10007로 나눈 나머지를 출력한다.