알고리즘 - DP / [백준] 11726. 타일링 - Python

• DP : Dynamic Programming
  • 이전의 값을 재활용 하는 알고리즘
  • 예시 : 1~10 숫자 중, 각각 이전 값들을 합한 값 구하기
  • 이전의 값을 활용해서 시간 복잡도를 줄일 수 있음

---

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

11726번: 2×n 타일링

---

• 생각
  • n이 1이면 1
  • n이 2이면 2
  • n이 3이면 1+2
    • A(n) = A(n-1) + A(n-2)

 

• 코드

from sys import stdin
input = stdin.readline

# 2Xn 크기의 직사각형
n = int(input())

# 결과
result = [0,1,2]

for i in range(3,n+1):
    result.append((result[i-1]+result[i-2])%10007)

print(result[n])