[백준] #1793 타일링

📌문제

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

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

입력

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

출력

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

제한

• 0 ≤ n ≤ 250

예제 입력

2
8
12
100
200

예제 출력

3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251

백준 1793번 문제

💡Idea

n이 1일 때부터 하나씩 늘려가면서 몇 번 경우의 수를 찾아보니, 앞 단계의 결과값들이 사용되는 것을 알았습니다.
따라서 이 문제는 동적계획법(dynamic programming)을 사용하여 해결할 수 있습니다.

• n이 1인 경우 : 1
• n이 2인 경우 : 3
• n이 3인 경우 : 5
• n이 4인 경우 : 11

점화식은 다음과 같이 만들 수 있습니다.

$d[i] \;= \;d[i -1] \; + \;2 \times d[i-2]$

💻코드1

import sys
input = sys.stdin.readline

dp = [0 for _ in range(251)]
dp[0], dp[1], dp[2] = 1, 1, 3
while True:
    try:
        n = int(input())
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + 2 * dp[i - 2]
        print(dp[n])
    except:
        break

📝코드 설명1

변수

• dp : n에 따른 방법의 수를 저장하는 DP의 memoization을 위한 리스트

동적계획법(Dynamic Programming)을 반복문을 통한 bottom-up으로 구현한 코드입니다.

먼저, dp를 모두 0으로 초기화한 뒤, n의 값이 0, 1, 2인 것은 1, 1, 3의 값을 넣어줍니다.

그리고, 숫자를 입력받으면 3에서부터 n까지 반복문을 돌며 점화식을 계산하여 최종적으로 계산된 dp[n]을 출력해줍니다.

해당 문제는 입력의 길이나 종료 조건을 주지 않았기 때문에, try-except문을 사용하여 비정상 종료되지 않도록 처리해주어야 합니다.

💻코드2

import sys
input = sys.stdin.readline

def tiling(dp, n):
    if dp[n] > 0:
        return dp[n]
    else:
        dp[n] = tiling(dp, n - 1) + 2 * tiling(dp, n - 2)
        return dp[n]

dp = [0 for _ in range(251)]
dp[0], dp[1], dp[2] = 1, 1, 3
while True:
    try:
        n = int(input())
        print(tiling(dp, n))
    except:
        break

📝코드 설명2

동적계획법(Dynamic Programming)을 재귀함수를 통한 Top Down으로 구현한 코드입니다.

tiling 함수

• 이미 계산된 값이면(dp[n] 값이 0보다 크다면) 그 값(dp[n])을 return합니다.
• 그렇지 않으면 점화식에 따라, 함수를 재귀 호출하여 dp[n]을 계산하고 계산된 값을 return해줍니다.

⏰ 메모리와 시간

bottom-up으로 구현

• 메모리 : 30840 KB
• 시간 : 76 ms

top-down으로 구현

• 메모리 : 30840 KB
• 시간 : 76 ms

두 가지 구현 방식에 따라 메모리 사용과 시간에서는 크게 차이가 나지 않음을 알 수 있었습니다.