[백준 1793번] 타일링 (python)

문제링크 : https://www.acmicpc.net/problem/1793

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

while(True):
    try:
        n = int(input())
        dp[0]=1 
        dp[1]=1
        dp[2]=3
        dp[3]=5

        for i in range(4, n+1):
            dp[i] = dp[i-1] + 2*dp[i-2]
        print(dp[n])
    except:
        break

 

출력 범위로 인해 python으로 푼 문제이다.

C++로 풀 경우 큰 수를 다뤄야 하기 때문에 훨씬 복잡해진다.

 

점화식의 경우 N=3 까지 그림을 직접 그려보면 어렵지 않게 알 수 있다.

N=3의 경우

N=1일때 가짓수에서 2*2 블록 추가한 케이스 2가지 (좌, 우 각 1개)

N=2일때 가짓수에서 2*1 블록 추가한 케이스 1가지 이렇게 총 3개의 케이스를 더하게 된다.

이를 점화식으로 나타내면 dp[i] = dp[i-1] + dp[i-2]*2가 된다.