[Python]11727번, 2×n 타일링 2

목차

 

문제

 

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

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

 

 

입력

 

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

 

출력

 

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

 

풀이

 

계속해서 수열의 규칙을 찾아 동적계획법으로 푸는 문제이다.

 

11726번 문제는 아예 피보나치수열과 그 규칙이 같아 생략하기로 했다.

 

이번 문제도 N을 1씩 증가시키며 규칙을 찾으면 간단한데, 우선 수열을 늘어놓으면 다음과 같다.

 

• 1, 1, 3, 5, 11, 21, ...

이를 굳이 수식으로 나타내자면 다음과 같이 쓸 수 있을 것이다.

 

$$a_{n} = 2 * a_{n-2} + a_{n-1}, (n \ge 2)$$

 

따라서 dp리스트를 만들고, dp[0]과 dp[1]을 1로 초기와 한 뒤 위 수식을 그대로 사용하면 된다.

 

Python

 

import sys

N = int(sys.stdin.readline().rstrip())
dp = [0] * (N + 1)
dp[0] = 1
dp[1] = 1

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

print(dp[N])

풀이과정을 이용해 그대로 dp 리스트를 채운 뒤 출력했다.

 

처음엔 규칙을 잘못 찾아 헷갈렸으나, 아직까지는 제대로 수열의 규칙만 파악하면 풀리는 문제들 뿐이다.

 

끝!