BOJ 11727번

https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

점화식을 어떻게 세우는지가 중요하였습니다.

 

늘 비슷한 DP 문제라도 꼼꼼하게 점화식을 만들어가야 풀 수 있었습니다.

def number_of_tiling(n):
    dp0 = 1
    dp1 = 1
    for i in range(1, n):
        temp = dp0
        dp0 = dp0 + (dp1*2)
        dp1 = temp

    return dp0 % 10007

n = int(input())
print(number_of_tiling(n))

1

1 + 1*2

(1+1*2) + 1*2

((1+1*2) + 1*2) + (1*2)*2

.... 

i번째의 타일링을 계산할 때 i-1번째에서 온 모양을 전부 그려보면

i-2번째에서 온 i번째 타일링이 하나도 포함되지 않은걸 알 수 있습니다.

 

i-2번째의 경우 2*1과 2*2 두개의 경우가 추가되기 때문에 (i-2)*2를 해주면 i-2번째에서 온 i번째의 타일링 갯수를 구할 수 있습니다.

 

i = (i-1) + (i-2*(2))