[Python] 백준 1793번 - 타일링 (DP)

 

 

<코드>

dp = [0 for i in range(251)]

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

 

풀이 방법

 

점화식을 생각해보면 dp[i]가 가질 수 있는 경우의 수는

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

dp[i-2]에서 2x1의 타일 두 개를 세로로 붙인 경우는 위의 경우 중 1번 경우에 포함되어있으므로 세지 않습니다.

따라서

점화식은 dp[i] = dp[i - 1] + 2 * dp[i - 2]이고

n이 0인 경우도 있으니 주의하시기 바랍니다.

 

이 문제는 테스트 케이스 개수가 주어지지 않으므로 try & except 구문으로 EOF Error를 처리하였습니다.

 

 

 

www.acmicpc.net/problem/1793

1793번: 타일링