[백준/Python] 11726 2*n 타일링

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

 

 

사용 알고리즘: DP

 

 

2 * n  크기의 직사각형을 1 * 2, 2 * 1 타일로 채우는 방법의 수를 구하는 문제 -> 전형적인 DP 문제

 

 

주어진 직사각형을 채우기 위한 방법의 수를 구하기 위해 도미노를 쪼개어 생각해보자. 

1 * 2 / 2 * 1 의 두 가지 타일로 주어진 직사각형의 가장 오른쪽 부분을 채우는 방법을 생각해보면 아래와 같이 2가지 방법이 있다. 

-> dp[n] = dp[n-1] + dp[n-2]

 

 

# 입력
n = int(input())

# dp 초기화, 인덱스 1 부터 사용할 것이기 때문에 1001 칸을 만들어줌
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)