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

 

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

11726번: 2×n 타일링

 

---

풀이

이 문제는 우선 규칙을 찾는 것이 먼저라고 생각들었다. 그래서 아래와 같이 일정 수까지 직접 구해보았다.

1	1
2	2
3	3
4	5
5	8
6	13
7	21
8	34
9	55

위의 표를 보면 2Xn의 크기를 타일링 하는 가지수는 (n-1) + (n-2)인것을 확인할 수 있다.

위에서 찾은 방법을 코드로 옮기면 아래와 같다.

n=int(input())
arr=[0]*1001
arr[1]=1
arr[2]=2
if n<3:
    print(arr[n])
else:
    a=3
    while True:
       arr[a]=arr[a-1]+arr[a-2]
       if a==n:
           print(arr[a]%10007)
           break
       a+=1