[파이썬/백준 11726]2×n 타일링

문제

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

 

접근

그림을 보면 위와 같은 규칙을 찾을 수 있다. 피보나치 수를 구해주면 된다. 예전에 피보나치 수를 구하는 문제에서 정직하게 재귀를 사용했다가 시간초과가 나오고, 배열에 저장해도 시간초과가 나왔던 기억이 있다. 그래서 변수만 사용해서 답을 구했다.

 

코드

n = int(input())
if n < 3:
    print(n%10007)
else:
    a, b = 1, 2
    for _ in range(n-2):
        a, b = b, a+b
    print(b%10007)