백준: 11727 2xn 타일링 2

문제

11727번: 2×n 타일링 2

 

문제 풀이

 이 문제는 2 x n 타일링 문제에서 2 x 2 타일이 추가 되어, 사용할 수 있는 타일이 2 x 1, 1 x 2, 2 x 2로 3개인 경우에 2 x n의 공간에 타일을 붙일 수 있는 경우의 수를 구하는 문제이다.

 

Figure 1. n에 따른 타일링 경우의 수

 그림 1을 보면, n이 증가함에 따라 1, 3, 5, 11, 21과 같은 규칙을 보이는 것을 알 수 있으며 이를 식으로 나타내면 f(n) = f(n - 1) + 2 * f(n - 2)가 된다. 따라서 해당 식을 코드로 작성하면 문제를 해결할 수 있다.

 

코드

from sys import stdin


if __name__ == "__main__":
    n = int(stdin.readline())
    a, b = 1, 3
    for _ in range(1, n):
        a, b = b, a * 2 + b
    print(a % 10007)