BAEKJOON #1793 (DP) - python

nathan·2021년 8월 3일
0

알고리즘문제

목록 보기
26/102

타일링

출처 : 백준 #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
profile
나는 날마다 모든 면에서 점점 더 나아지고 있다.

0개의 댓글