[알고리즘][Python] 백준(BOJ) 1793 타일링_파이썬

 

1793 타일링    www.acmicpc.net/problem/1793

1793번: 타일링

 

 

 

 

문제 풀기 전 공부할 것 : 다이나믹 프로그래밍

 

 

 

 

 

 

 

풀이

<내용>

• n이 0, 1, 2일 때를 초기화한다.
• n번째 직사각형을 채우는 방법은 n-1번째 직사각형에서 2x1 타일을 더하는 방법과 n-2번째 직사각형에서 2x2 타일을 더하는 방법, 2x1 가로 2개 타일을 더하는 방법이 있다.
• n마다 직사각형을 채우는 방법을 출력한다.

 

 

<코드>

import sys
input = sys.stdin.readline

def solve(n):
    dp = [1, 1, 3]
    for i in range(3, n+1):
        dp.append(dp[i-1] + dp[i-2]*2)
    return dp[n]
    
while True:
    n = input().rstrip()
    if n.isdigit():
        print(solve(int(n)))
    else:
        break