[ Baekjoon : python ] 백준 11727 2×n 타일링 2 - 다이나믹프로그래밍

[  BAEKJOON ONLINE JUDGE  ] 11727 2×n 타일링 2_ Python 파이썬

 

" 문제 "

 

www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

---

" 아이디어 "

 

기본 아이디어는 2xn 타일링 (1) 문제와 유사하다.

 

 ↓ 2xn 타일링 (1) 문제 풀이

[ Baekjoon : python ] 백준 11726 2xn 타일링 - 다이나믹프로그래밍

타일링 (1) 과 다른 점은 타일의 가로의 길이가 2인 경우 경우의 수가 2가지가 생긴다는 것이다.

 D[n] = 주어진 2 * n 직사각형을 채우는 경우의 수

 

맨 끝 타일을 1 * 2 타일로 채울 경우 -> D[n-2]

맨 끝 타일을 2 * 2 타일로 채울 경우 -> D[n-2]

맨 끝 타일을 2 * 1 타일로 채울 경우 -> D[n-1]

 

D[n] = D[n-1] + D[n-2] * 2 (n>=3)

D[n] = 1 (n=1)

D[n] = 3 (n=2)

---

" 코드 "

 

import sys
sys.setrecursionlimit(10000000)
 
def calc(n):
  if n==1: return 1
  if n==2: return 3
 
  if m[n] == 0:
    m[n] = calc(n-2)*2 + calc(n-1)
  
  return m[n]
 
n = int(input())
m = [0]*(n+1)
print(calc(n)%10007)

 

---

" 참고자료 "