https://www.acmicpc.net/problem/11727
11727번: 2×n 타일링 22×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다.www.acmicpc.net
2xn 타일링 1과 비슷한 문제이다.
n[i]=n[i-2]*2+n[i-1]이라는 점화식을 세울 수 있다.
왜?
i번째를 채우기 위해서는
i-1번째의 경우에서 2*1 타일 1개를 채우는 방법과,
i-2번째의 경우에서 12 2개로채우는 방법, 22 1개로 채우는 2가지 방법이 있기 때문이다.
i-1번째의 경우는 그대로, i-2경우에는 각각 2개의 경우이므로 *2를 해주면 된다.
사실 0개를 채우는 경우의 수는 0이지만, 곱셈연산을 위해 편의상 1로 가정하고 코드를 짰다.
n=int(input())a,b=1,1cnt=1while cnt<n: a,b=b,a*2+b cnt+=1print(b%10007)