백준_python 11726번 2×n 타일링(DP)

<문제 링크>

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

 

 

 

<정답 코드>

n = int(input())
 
nums = [1,1]
 
for i in range(2, n+1):
    nums.append(nums[i-2] + nums[i-1])
 
print(nums[n] % 10007)

 

문제를 읽어보고 규칙성이 있을 것 같아 몇 개를 그림으로 그려 보니 아래와 같았다.

n	방법의 수
2	2
3	3
4	5
5	8

 

피보나치 수로 진행되는 것이 보여 간단하게 문제를 해결했다. 

DP(동적 프로그래밍) 문제였는데, 큰 문제를 작은 문제로 쪼개는 원리가 피보나치에도 적용되어 있었다.

 

 

 

 

DP를 얼른 공부해야겠다.