[백준] 11726번 문제 (2 x n 타일링) 파이썬(Python) 풀이

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

for i in range(3, 1001):
  dp.append(dp[i - 2] + dp[i - 1])

print(dp[n] % 10007)

처음에는 도대체 어떻게 풀어야 하나... 고민이 많았는데 참 단순한 문제였다.

직접 메모장에 경우의 수를 그려가며 직사각형을 채우는 방법의 수를 구해보면 알 수 있는데 

 

n을 기준으로

1개면 : 1

2개면 : 2

3개면 : 3

4개면 : 5

5개면 : 8

6개면 : 13

7개면 : 21

8개면 : 34

9개면 : 55

방법의 수가 나온다.

그러면 숫자의 규칙이 보일 것이다.

 

바로 dp[i] = dp[i - 1] + dp[i - 2] 라는 규칙이 성립되고, 이것을 for문을 반복하며 n번 까지의 방법의 수를 구하면 된다.