[python]백준 11726 풀이

한상욱·2023년 7월 27일

python 다이나믹프로그래밍 백준

[python]백준풀이모음

목록 보기

5/38

2xn 타일링

백준 11726 문제 링크

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

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

출력

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

풀이

일단, n에 값에 따라서 어떻게 채울 수 있는지 나열해보겠습니다.

$n=1$ 인 경우, 한가지밖에 없겠죠?

$n=2$ 인 경우, 두가지 방법이 존재합니다.

$n=3$ 인 경우부터 2가지 방법으로 나누어서 타일링 방법을 셀 수 있습니다.

첫번째로 맨 처음 타일이 그냥 세로로 놓여있는 경우, 남은 타일은 2개의 타일이 들어갈 수 있습니다. 이 경우에는 $n=2$ 인 경우의 수랑 동일하겠죠?

두번째로 맨 처음타일과 두번째 타일이 함께 가로로 놓인 경우, 남은 타일은 세로로 한개가 들어갈 수 있고, 이건 $n=1$ 인 경우와 같습니다.

그래서 총 1+2=3가지 경우가 있습니다.

$n=4$ 인 경우도 두가지의 경우로 나누어서 생각하면 첫 타일이 세로로 고정된 경우, 뒤에 남은 타일은 세로로 3개가 들어갈 수 있으니 당연히 $n=3$ 인 경우와 같겠죠?

뒤에 3칸만 다르게 변경됥테니까요.

첫번째와 두번째타일이 가로로 누워있는 경우에는 $n=2$ 인 경우와 똑같겠죠?

그렇다면 $i$ 인 경우의 수를 $a_i$ 라고 하였을 때, 점화식은 다음과 같다고 할 수 있습니다.

a_1 = 1, a_2=2

a_i = a_{i-1}+a_{i-2} (n \geq3)

이 경우에는 다이나믹 프로그래밍으로 해결할 수 있겠죠? 왜냐하면 다이나믹 프로그래밍이 성립하는 두가지 경우를 모두 만족하니까요. 이제 점화식을 바탕으로 상향식 방식으로 풀이를 작성하겠습니다.

import sys

dp = [0] * 1001 # dp 테이블 초기화
dp[1] = 1 # 1인 경우는 1
dp[2] = 2 # 2인 경우는 2
n = int(sys.stdin.readline())
for i in range(3, n+1):
	# 점화식 표현
    dp[i] = dp[i-2] + dp[i-1]

print(dp[n] % 10007) # 나머지 출력인 점 중요