[백준][파이썬][DP] 11726번: 2xn 타일링

문제집: 

https://www.acmicpc.net/workbook/by/BaaaaaaaaaaarkingDog

 

 

 

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

 

 

 

문제

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

 

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

 

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

 

 

 

예제 입력 1 

2

 

예제 출력 1

2

 

예제 입력 2 

9

 

예제 출력 2 

55

 

---

 

import sys 

if __name__=="__main__":
    N=int(input())
    dp = [0]*(N+1)
    dp[1]=1
    if N>1:
        dp[2]=2
        for i in range(3,N+1):
            dp[i] = dp[i-2] + dp[i-1]
            
    print(dp[-1]%10_007)

 

 

 

n=1 : 1

2x1 한개

n=2 : 2

1x2 2개 쌓기

2x1 2개 세우기

n=3 : 3

2x1 3개 세우기

2x1 1개 + 1x2 2개 쌓기

1x2 2개 + 2x1 1개

n=4 : 5

2x1 4개

2x1 2개 + 1x2 2개

2x1 1개 + 1x2 2개 + 2x1 1개

1x2 2개 + 2x1 2개

1x2 4개

n=5 : 8

|||||

|||=

||=|

|=||

=|||

|==

=|=

==|

 

 

규칙을 찾자