백준 알고리즘 파이썬(Python) 1793번 타일링

---

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

1. dp [ i-1 ] 에서 추가로 2x1의 타일을 세로로 붙인 경우
2. dp [ i-2 ] 에서 추가로 2x1의 타일을 가로로 2개 붙인 경우 + 2x2의 타일을 하나 붙인 경우

이렇게 점화식을 구성할 수 있다.

(여기서 주의할 점은 dp[ i -2 ]에서 2x1 타일을 세로로 2개 붙인 경우는 1번 경우 안에 포함됨으로 점화식에 포함시키지 않는다.)

 

따라서 최종 점화식은 

dp[i] = dp[i - 1] + 2 * dp[i - 2]

 

(여기서 i = 0일때 즉 타일을 아무것도 놓지 않는 경우도 1로 세준다는 것에 주의하자)

 

이 문제는 테스트 케이스의 개수가 주어지지 않기 때문에 예외처리를 통해 구현해준다.

 

---

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