타일 문제

1. 정답 코드

문제의 정답 코드는 다음과 같다.

n = int(input())
d = [0] * 1001

d[1] = 1
d[2] = 3

for i in range(3,n+1):
    d[i] = d[i-1]+2*d[i-2] % 796796

print(d[i])

이번 문제를 풀면서 가장 느낀건 DP문제는 점화식만 세울 줄 알면 되는 것 같다. 문제는 점화식을 세우는 방법을 파악하는 것이 포인트. 문제를 많이 풀어봐야 할 것 같다.

이 타일 문제는 가장 기본적인 문제 중 하나인데, 나는 규칙은 보이는데 이걸 어찌해야할 지 몰랐었다. 근데 그냥 아주 간단히 해결하는 방법이 있어서 놀랍네.. 근데 그 해결방법조차 점화식이 왜 그렇게 되는지 몰랐다. 그래서 계속 파헤치던 중 깨달음을 얻었지만, 글로 쓰기에는 설명이 너무 힘들어서 그냥 동영상을 찍어버렸다~~

2. 문제 풀이