바닥 공사

다이나믹 프로그래밍은 종종 결과가 너무 클 수 있어서 어떤 수로 나눠서 출력하라고 한다.

 

풀이법

-N이 3일 때의 예시

1. N이 3이고, i-1번째 즉, 2번 칸까지 채워져 있으면 경우에 수는 1개이다.

2. i-2번째 즉, 1번 칸까지 채워져 있으면 경우의 수는 2가지이다.

 

-점화식

따라서 점화식은 이렇게 구할 수 있다.

 

풀이

n = int(input())

d = [0] * 1001
d[1] = 1
d[2] = 3

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

print(d[n])

점화식에 맞게 코딩을 했다. 이 문제의 풀이도 처음엔 생각하지 못했다. 다이나믹 프로그램을 코딩하면 쉽지만 점화식 같은 풀이를 생각하는 것이 어렵다. 앞으로 더 많은 연습을 해야겠다.