[백준] [Python] 11726번_2xN 타일링_다이나믹 프로그래밍

문제

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

11726번: 2×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)

이 문제를 풀기위해 다이나믹 프로그래밍을 사용하였다. 

처음 d 배열을 n의 갯수만큼 선언해주고 점화식을 구하려고 하였다. 

타일 배열의 경우의 수를 살펴보았는데 칸수가 늘어나게 될수록

늘어난 타일에 대한 경우의 수 + 그 전 타일의 경우의 수 라는 것을 알게되었다.  

그 결과 d[i] = d[i-1] + d[i-2] 라는 점화식을 구하게 되었고 이를 코드로 구현하였다. 

i가 1과 2일 경우는 명확하기 떄문에 처음에 선언을 해주었다.