[백준][11727] 2xn 타일링 2

• Problem Link : https://www.acmicpc.net/problem/11727

문제

2xn 직사각형을 1x2, 2x1, 2x2 타일로 채우는 방법의 수를 구하여라

입력

• 첫째 줄, n이 주어진다.

출력

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

풀이

전형적인 다이나믹 프로그래밍 문제로 n까지 반복문을 돌리면서 i번째의 원소에는 i번째 올 수 있는 방법의 수를 구한다. 그렇다면 i번째에 올 수 있는 방법의 수는 무엇일까? 이 때 타일은 오른쪽으로 붙이면서 진행한다고 하자.

이 때 i-1, i-2,···, 1번째의 방법의 수를 안다고 가정해보자.

1. 2x(i-1) 길이 타일에 1x2 타일을 붙이는 경우
2. 2x(i-2) 길이 타일에 2x1을 위, 아래 이어붙여 붙이는 경우
3. 2x(i-2) 길이 타일에 2x2 타일을 붙이는 경우

따라서 i번째 타일 방법의 수를 f(i)라고 한다면 $f(i) = f(i-1) + 2 * f(i-2)$라고 할 수 있다.

이를 다른 말로 하면 i-1 번째와 i-2 번째 방법의 수를 구할 수 있다면 i번째 타일을 놓는 경우의 수도 구할 수 있다는 말이다. 그 말은 1, 2번째 수를 안다면 3, 4, ···, n번째 방법의 수도 구할 수 있다는 뜻이다.

• 2x1 타일을 채우는 방법은? 1x2 타일 하나로 채우기 = 1
• 2x2 타일을 채우는 방법은? 1x2 타일 두 개로 채우기 + 2x1 타일 두 개로 채우기 + 2x2 타일 하나로 채우기 = 3

이제 반복문을 돌려서 n번째 원소를 구하면 해당 값이 2xn 타일을 채우는 방법의 수다.

11726번 문제도 동일하게 규칙을 찾으면 풀 수 있다.

코드

import sys

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