[파이썬] 백준 11726 2 x n 타일링

 

# 백준 11726 2xN 타일링
n = int(input())

d = [0] * 1001
d[1] = 1
d[2] = 2
for i in range(3, n + 1):
    d[i] = d[i-1] + d[i-2]

print(d[n] % 10007)

 

보텀업 방식

다이나믹 프로그래밍 : 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘

 

계산된 결과를 저장하기 위한 DP 테이블 초기화 

d = [0] * 1001

 

첫번째 수 두번째 수 대입

 

반복문으로 구현 - 보텀업 다이나믹 프로그래밍

 

** 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 부분 문제의 중복 여부를 확인해보자. **

 

점화식

d[n] = d[n-1] + d[n-2]