[python]11727번 2×n 타일링 2

2×n 타일링의 응용문제로 점화식 공부하기 좋은 문제인것 같다

이 문제 또한 계단 문제처럼 점화식을 떠올렸다.

 

계단문제로 비유를 해서 푼 방법은 다음과 같다

n칸짜리 계단이 있다.

계단을 올라가는 방법은 3가지 있다.

1칸 올라가기, 주머니 손 넣고 2칸 올라가기, 그냥 2칸 올라가기(3 경우 모두 다른 경우이다)

여기서 왜 2칸 올라가는 것을 2가지로 나눴냐면

타일에서 2칸을 채우는 방법이 2*2칸으로 채우거나 2*1칸 두개를 합쳐서 2*2를 합치는 경우이기 때문이다.

초기항으로 1번째 칸은 1가지 경우

2번째 칸은 3가지이다

그러면 3번째 칸은 몇가지 일까

 

먼저 2번째칸에서 3번쨰 칸 가는 방법은 1칸 올라가는 경우이다.

이 경우에는 2번쨰 칸까지 올라가는 수가 그대로 3번째칸까지 가는 경우와 같다

그러면 1번째 칸에서 3번쨰 칸 가는 방법은 무엇일까

바로 주머니에 손넣고 2칸 올라가거나, 그냥 2칸 올라가는 것이다.

이는 1번째 칸 경우의 수에서 2갈래로 찢기기에 곱하기 2를 해주고 더해야한다.

 

이를 바탕으로 점화식은

n = (n-2)*2+(n-1) n번쨰 칸의 경우의 수는 n-2에 2곱한 값과 n-1번쨰 값을 더한 값과 같다.

call = int(input())
fst = 1
scd = 3
rst = call if call!=2 else 3
for i in range(3,call+1):
    rst = (fst*2+scd)%10007
    fst = scd
    scd = rst
print(rst)