BAEKJOON 1793 : 타일링

Dynamic programming의 대표 예제인 타일링 문제이다.

Dynamic programming 문제인 만큼 점화식을 세워서 풀었다.

 

이 문제에서 점화식은 d[i] = (d[i-1] + d[i-2]*2)로 구할 수 있다.

 

왜냐하면 타일이 i-1까지 모두 채워져 있을 경우에는 타일을 채울 수 있는 경우가 한 가지밖에 없고, 타일이 i-2까지 모두 채워져 있을 경우에는 타일을 채울 수 있는 경우가 두 가지가 있기 때문이다.

 

나는 파이썬으로 풀었다.

다음은 파이썬 코드이다.

 

def dynamic(num):
    d = [0]*251
    d[0] = 1
    d[1] = 1
    d[2] = 3
    for i in range(3, num+1):
        d[i] = (d[i-1]+d[i-2]*2)
    print(d[num])

while True:
    try:
        n = int(input())
        dynamic(n)
    except:
        break