[백준] 11726 '2×n 타일링' 파이썬(python)

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

11726번: 2×n 타일링

n = int(input())

dp = [0] * 1001		# DP 테이블 만들기. 주어진 범위가 1000이라서 1001까지 받는다.
dp[1] = 1
dp[2] = 2

for i in range(3,1001):
    dp[i] = dp[i-1] + dp[i-2]		# 발견한 점화식을 사용. 피보나치 수열과 같다.

print(dp[n] % 10007)

Point

• DP를 이용한 알고리즘 문제
• 바텀업 방식으로 작은 문제 해결을 바탕으로 큰 문제를 푼다.
• 각 규칙을 찾다보니 점화식을 찾게 되었고 해당 점화식을 활용하여 푸는 문제.