[백준] 11727 2xn 타일링 2

DP에 관련된 문제를 풀어보던 중  기초 예제로 자주 나오는 타일링 문제 유형을 정리하면 좋을 것 같았다.

다음 문제를 풀어보자.

---

문제

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1

2

예제 출력 1

3

예제 입력 2

8

예제 출력 2

171

예제 입력 3

12

예제 출력 3

2731

---

위 문제는 어떻게 접근해야할까? DP 문제의 핵심은 규칙을 찾아서 점화식을 찾는 것이다. 규칙을 찾아보면 다음과 같다 ⭕️

점화식을 만들었으니 코드로 작성해보자!

import sys

input = sys.stdin.readline
n = int(input()) # 정수 N 입력

dp = [0] * 1001 # 결과를 저장하기 위한 DP 테이블 초기화

# DP 진행(보텀업)
dp[1] = 1
dp[2] = 1

# 점화식에 따른 경우의 수 계산
for i in range(3, n+1):
    dp[i] = dp[i-1] + 2 * dp[i-2]

print(dp[n]%10007)

코드는 다음과 같이 간단하나 처음 이러한 유형의 문제를 접할 경우 어려움을 느낄 것 같다.

💡 DP 타일링 유형은 잘 정리해서 해당 유형 나오면 다 맞추기 🔥🔥🔥🔥🔥🔥

---

 

Reference

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

11727번: 2×n 타일링 2