[백준] 11726번: 2xn 타일링 (점화식 직접 찾기)

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

---

import sys 

sys.stdin = open("input.txt")

n = int(sys.stdin.readline().rstrip())

dp = [0] * 1001

dp[1] = 1
dp[2] = 2

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

print(dp[n])

 

알고리즘 분류:

- 다이나믹 프로그래밍

 

Key Points:

직접 케이스 별 값을 찾은 다음 점화식을 세워봤더니 dp[i] = dp[i-1] + dp[i-2]가 나왔다. 조금 더 원리적으로 파고 들어가면 왜 이런 점화식이 도출되는지 알 수 있겠지만 사실 이런 문제는 그냥 직접 점화식을 찾고 넘어가는게 정신 건강에 좋을 것 같다...