[BOJ] 2xn 타일링 2 (no.11727)

문제

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

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

입력

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

출력

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

🤔 생각

• 언제나 그렇듯 케이스를 나누자. 잔재주보단 케이스 완벽분할에 집중해야한다.

케이스

1. 타일이 1열만 비었을 경우

• 2x1

2. 타일이 2열만 비었을 경우

• 1x2 1x2
• 2x2
• (2x1 2x1 은 케이스 1에 포함되므로 점화식에 미포함)

배열 정의

dp[i] : i번째 열까지 타일 놓는 경우의 수

🔥 점화식
dp[i] = dp[i-1] + dp[i-2]*2

📌 내 풀이

import sys
input = sys.stdin.readline

n = int(input())
dp = [0,1,3]

for i in range(3,n+1):
    dp.append(dp[i-1] + 2*dp[i-2])

print(dp[n]%10007)

✔ 회고

• 생각보다 메모이제이션 요소를 뭐로 삼을지가 상당히 중요한 것 같다.
• 웬만하면 문제의 조건에 따라 최솟값, 최대 경우 등등을 dp[i]로 잡는데 그렇지 않은 경우도 있다.