[백준] Silver 3. 11727 - 2xn 타일링 2 python

문제 링크

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

---

문제 설명

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

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

 

입력

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

 

출력

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

---

제출 코드

import sys

input = sys.stdin.readline
n = int(input().rstrip())
dp = [0 for _ in range(1001)
dp[1] = 1
dp[2] = 3
dp[3] = 5

if n > 3:
    for i in range(4, n+1):
        dp[i] = dp[i-1] + 2*dp[i-2]

print(dp[n]%10007)

 

풀이

• 2xn 타일을 채울 수 있는 방법의 수를 구하는 문제이다. 이 때, 타일의 종류가 1x1, 2x1, 2x2로 세가지 종류가 있다.
• 2x4 타일을 채우는 경우를 생각해 보면, 2x3 타일을 만드는 경우에 1x1 타일을 더하는 경우와, 2x2 타일을 만드는 경우에 2x1 타일 두개를 더하는 경우, 2x2 타일 하나를 더하는 경우가 있다.
  • 점화식으로 표현하면 다음과 같다. : dp[i] = dp[i-1] + 2*dp[i-2]

 

알아둘 사항

• 다음 단계로 갈 때 어떻게 갈 수 있는지 최대한 쪼개서 생각해보자~!