백준 11726 파이썬(DP)

예전에 공부할때 봤었던 이코테라는 책에 이 문제와 비슷한 유형이 있어서 쉽게 풀 수 있었다.

 

피피티로 만들어본...긁적긁적...

타일을 채우는 방법의 수를 구하는 문제인데

m(n) = m(n-1) + m(n-2)로 

결국 피보나치 수열과 같다.

 

피보나치 수열은 DP의 대표적인 문제로 재귀와 반복문 둘다 풀이가 가능하고 둘다 알아놓으면 좋을 듯 하다.

이번에는 바텀업 방식으로 풀어보았다.

마지막에 10007로 나눈 나머지를 출력하는 것을 까먹으면 안된다 ㅠㅠ 

이걸 놓쳐서 10분동안 "어.. 왜 안되지...??" 를 반복했다.ㅠㅠ

# 11726번: 2xn 타일링

n = int(input())

m = [0]*1001
m[0] = 0
m[1] = 1
m[2] = 2

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

print(m[n]%10007)