[백준] 11727 | 2xn 타일링 2 [파이썬/python]

문제

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

1x2, 2x1, 2x2 크기 타일을 활용해 2xn 사이즈 직사각형을 채우는 경우의 수를 구해 10007로 나누었을 때의 나머지 값을 출력하는 문제이다.

 

접근

백준 11726번 2xn 타일링 문제와 같은 방식으로 접근하면 된다. (https://going-on.tistory.com/46)

[백준] 11726 | 2xn 타일링 [파이썬/python]

2xn 타일링에서는 1x2 타일과 2x1 타일 두 가지를 사용할 수 있었고, 2xn 타일링 2에서는 2x2 타일이 추가되었다. 따라서 2x(n-1) 크기 직사각형 끝에 2x1 타일을 추가하는 경우(f(n-1)), 2x(n-2) 크기 직사각형 끝에 1x2 타일 두 개 혹은 2x2 타일 하나를 추가하는 경우(2*f(n-2))의 합을 계산하여 출력하면 된다.

 

%10007 처리하는 것 또한 잊지 말아야 한다!

 

코드

n = int(input())

a = [0, 1, 3] + [0]*(0 if n < 3 else n - 2)

for i in range(3, n + 1):
    a[i] = (a[i-1] + (2 * a[i-2])) % 10007

print(a[n])