[백준 1793] 타일링 - python

원본 문제 링크 : 타일링

문제

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

입력

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

출력

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

제한

• 0 ≤ n ≤ 250

풀이

DP 문제이다. 만약 부분 문제의 결과값을 저장하는 배열 dp에서 dp[i]가 가질 수 있는 경우의 수는

1. dp[i-1]에서 $2\times 1$의 타일을 세로로 붙인 경우
2. dp[i-2]에서 $2\times 2$의 타일을 붙인 경우
3. dp[i-2]에서 $2\times 1$의 타일 두 개를 가로로 붙인 경우
4. dp[i-2]에서 $2\times 1$의 타일 두 개를 세로로 붙인 경우

여기서 4번은 1번의 경우에서 포함되므로 세지 않는다.

따라서 점화식은 다음과 같다. \(dp[i] = dp[i-1]+2\times dp[i-2]\)

소스 코드

#bottom-up
memo = [0]*251
memo[0] = 1
memo[1] = 1
memo[2] = 3
for i in range(3,251) : #bottom-up 방식으로 배열을 채움
    memo[i] = memo[i-1] + memo[i-2] * 2
while True : 
    try : #테스트 케이스의 개수를 저장해 놓지 않아서 예외처리를 통해 종료하도록 설정
        n = int(input())
    except :
        break
    print(memo[n])

# Top-Down
def search(n):
    if n <= 2:
        return memo[n]
    if memo[n] != 0:
        return memo[n]
    memo[n] = search(n-1) + search(n-2) * 2
    return memo[n]

memo = [0] * 251
memo[0] = 1
memo[1] = 1
memo[2] = 3

while True:
    try:
        n = int(input())
    except:
        break
    print(search(n))

채점 결과 상으로 시간 복잡도, 공간 복잡도가 모두 같았다.