[BOJ] 11727번 : 2xN 타일링 2

🔒 문제

⌨ 입력

🖨 출력

📚 예제

📌 풀이

위의 그림을 보면 n이 1이고, 2인 경우를 제외하면 n이 3부터는 규칙이 생기는 것을 알 수 있다.

2 x n을 만들기 위해서는 2가지 방법이 있다.

1. 2 x (n - 1) 인 경우에 1 x 2 타일 1개 붙이기
2. 2 x (n - 2) 인 경우에 2 x 2 타일이나 2 x 1 타일 2개 붙이기

그래서 식으로 적으면 dp[n] = dp[n - 1] + dp[n - 2] * 2가 된다.

위의 그림을 보면 이해가 더 쉬울 것이다.

분홍색 형광펜으로 네모 표시를 한 부분들이 바로 이전 타일들에 추가된 부분들이다.

아래는 dp 식을 정리한 것이다.

dp를 위한 배열을 만들 때, n이 아닌, n + 1 배열로 만드는 것이 편하다.

🔑 python 코드

# 2xN 타일링 2
import sys
input = sys.stdin.readline
n = int(input())

if(n == 1):
    print(1)
elif(n == 2):
    print(3)
else:
    dp = [0 for _ in range(n + 1)]
    dp[1], dp[2] = 1, 3
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2] * 2

    print(dp[n] % 10007)