2022.03.07 [백준] (python 파이썬) 2Xn 타일링 2

 

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

11727번: 2×n 타일링 2

 

---

풀이

이 문제는 n이 늘어날 때마다 수가 어떤 규칙을 가지고 늘어나는지를 찾아야 한다.

그래서 1~8까지 구하면 다음과 같다.

1	1
2	3
3	5
4	11
5	21
6	43
7	85
8	171

n일때 타일을 채우는 가지수는 2**n-(이전n일때 채울수 있는 가지수)가 된다.

이 규칙을 코드로 옮기면 아래와 같다.

 

n=int(input())
 
def Tail(n):
    a=1
    ans=1
    while a<n:
        ans=2**(a+1)-ans
        a+=1
    return ans%10007
 
print(Tail(n))