백준 문제 중 11726번, DP, ‘2xn 타일링’

백준 문제 중 11726번

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

문제

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

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

입력

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

출력

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

---

풀이

2 x n 의 타일링하는 방법을 구하는 함수를 tailng(n) 이라 하자. 2 x n 을 타일링 하는 방법은 2 x (n-1) 을 타일링 한후 2 x 1 모양의 타일을 끝에 붙이는 경우와 2 x (n-2) 을 타일링 한후 1 x 2 모양의 타일을 가로로 두개 쌓아 끝에 붙이는 경우의 합이라고 할 수 있다. 2보다 큰 모든 n에 대해 이 조건을 만족하므로 이를 코드로 나타나면 된다.

from collections import defaultdict

import sys

n = int(input())

dp = defaultdict(int)
 # 예외 처리
dp[1],dp[2] = 1,2

def tailing(n:int)->int:

     # dp[n]이 0이 아니라면 dp[n] 리턴
    if dp[n]:
        return dp[n]

     # n-2의 경우와 n-1의 경우의 합
    dp[n] = tailing(n-2) + tailing(n-1)

    return dp[n]

print(tailing(n)%10007)

9
55

배운점

규칙을 잘 생각해보면 점화식을 쉽게 생각 할 수 있는 문제였다.