[백준 11726 : PYTHON] 2xn 타일링

문제 풀기 : 11726번

11726번: 2×n 타일링

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하라.

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

문제풀이

다음은 n = 4 까지의 경우의 수를 따져본 것이다.

 

n = 3 부터 보면 n = 1과 n = 2의 타일 모양이 그대로 들어있고

n = 4 를 보면 n = 2와 n = 3의 타일 모양을 그대로 가지고 있다는 것을 알 수 있다.

해당 규칙을 파악한대로 점화식을 작성해보면

 

dp[i] = dp[i-2] + d[i-1]

 

이라는 결론을 낼 수 있다. 

 

전체코드

import sys
input = sys.stdin.readline

n = int(input())
dp = [0] * 1001

# 초기값 지정
dp[1] = 1
dp[2] = 2

# 점화식에 따른 경우의 수 계산
for i in range(3, n+1):
    dp[i] = dp[i-1] + dp[i-2]

print(dp[n]%10007)