타일링

출처 : 백준 #1793

시간 제한	메모리 제한
1초	128MB

---

문제

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

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

---

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 숫자 0 ≤ n ≤ 250이 주어진다.

---

출력

입력으로 주어지는 각각의 n마다, 2×n 직사각형을 채우는 방법의 수를 출력한다.

---

입출력 예시

예제 입력 1

2
8
12
100
200

예제 출력 1

3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251

---

풀이

생각

• 완전 탐색을 해야하는 문제이다.
• 중복되는 경우가 많다.
  • 즉 부분 문제의 해를 계속하여 이용한다.
  • 따라서 DP로 문제를 해결하려 하였다.
• Top down, Bottom up 방식 중 하나를 골라서 풀어야 했는데, base case를 작성하여 Bottom up 방식을 이용하였다.

풀이 설명

• DP 문제에서 가장 중요한 것은 점화식이다.
  • 이 문제에서의 점화식은 다음과 같다.
  • An = 2*An-2 + An-1
• n이 0일 때와 1일 때는 모두 1이므로 basecase를 작성할 수 있다.
• basecase를 바탕으로 bottom up 방식을 이용하였다.

• 여기서 어려웠던 것은 입력을 몇 개 받을지 주어지지 않고, 그때 그때 출력을 했어야 했는데 그 부분은 다음과 같이 해결하였다.

while True:
    try:
        print(tile(int(f())))
    except:
        break

python code(Bottom UP)

# 백준 1793번 타일링
from sys import stdin
f = stdin.readline

# bottom up
def tile(n):
    if n <= 1:
        return 1
    else:
        temp = [0 for i in range(n+1)]
        # base case
        temp[0] = 1
        temp[1] = 1
        for i in range(2, n+1):
            temp[i] = temp[i-1] + (2*temp[i-2])

        return temp[n]

while True:
    try:
        print(tile(int(f())))
    except:
        break