[이코테] 다이나믹 프로그래밍 - 바닥 공사

오랜만에 아예 감을 못 잡겠는 문제였다

 

1-1. 풀이 도중 생각

1) 주어진 조건이 무조건 2xN인 모양이라 그나마 생각이라도 좀 했는데, 아니었으면 아예 접근도 못했을듯

2) N이 짝수라면 2x1 블록이 없어도 괜찮고 N이 홀수라면 2x1 블록은 무조건 하나 있어야 한다

3) 그 뭐냐 sliding window처럼 슈슉 지나가면서 만들어내는 규칙 같은게 있을 것 같은데 모르겠다

4) 결과를 769,769로 나눈 나머지를 출력하라고 하는데 특이하다

 

2. 책 풀이

아니 이거 점화식 세우는거 어떻게 생각하는거임????? i-1번째, i-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] + 2 * d[i-2]) % 769769
    
print(d[n])

 

3. 새로 알게 된 것 or 새삼 다시 알게 된 것

없음... 걍 몰라...

이거 점화식 세우는 패턴 알기 전에는 문제 못 풀듯;