알고리즘 - Python / 백준 - 11726번 : 2Xn 타일링

11726번: 2×n 타일링 (acmicpc.net)

11726번: 2×n 타일링

 

---

풀이

• DP문제 이므로 점화식을 찾는다.
• 1, 2, 3, 4 단계까지 직접 찾아본후 첫 사각형이 세로 1개일때와 가로 2개일때로 구분하면 된다는 사실을 알았다
• 이를 통해 점화식 dp[i] = dp[i-1] + dp[i-2] 를 찾았다
• 전체 크기만큼 돌려 DP 배열을 모두 구한후 원하는 답을 출력하자

 

import sys

dp = [0]*1001
dp[0] = 0
dp[1] = 1
dp[2] = 2
dp[3] = 3

for i in range(4,1001):
  dp[i] = dp[i-1] + dp[i-2]

n = int(sys.stdin.readline())
print(dp[n]%10007)

---