[백준(Baekjoon)] 11726 2*n 타일링

문제

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

 

---

나의 코드

[Python(파이썬)]

n = int(input())
dp = [0, 1, 2]

for i in range(3, n+1):
    dp.append(dp[i-2]+dp[i-1])
print(dp[n] % 10007)

---

풀이

처음 이 문제를 보고 경우의 수를 다 어떻게 생각하지??

세로의 개수의 경우의 수를 따져서 생각해야하나? n이 짝수, 홀수일 때를 따로 봐야하나? 등 여러가지를 생각하다 n이 1일때 직사각형을 채울 수 있는 경우의 수부터 차례대로 한 번 그려봤다. 

 

 

 

 

그러다 규칙을 발견했는데 피보나치 수열과 같이 이루어지는 것이었다.

2×n 크기의 직사각형을 채우는 방법은 (2×(n-1)크기 직사각형 채우는 방법 개수) + (2×(n-2)크기 직사각형 채우는 방법 개수) 이다. 

---

문제 출처

11726번: 2×n 타일링