[백준] 11727번 : 2×n 타일링 2 (Python)

문제 : https://www.acmicpc.net/problem/11727

 

 

2×n 크기의 직사각형을 1×2, 2×1, 2×2 타일로 채우는 방법의 수를 구하는 문제다.

 

import sys

input = sys.stdin.readline

N = int(input())
DP = [0]*1001
MOD = 10007

# 초기값 세팅
DP[1] = 1
DP[2] = 3

# DP 테이블 생성
for i in range(3, 1001):
    DP[i] = (DP[i-1] + 2*DP[i-2])%MOD

print(DP[N]%MOD)

 

 

[문제풀이]

---

 

이 문제는 규칙 찾기, 즉 다이나믹 프로그래밍을 이용해서 풀 수 있다.

 

 

 

 

 

이걸 정리해 점화식으로 나타내면 이렇게 된다.

D[i] = D[i-1]+2*D[i-2]

 

이걸 이용해 바텀-업(Bottom-Up) 방식으로 문제를 풀면 끝!