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

🥚문제

---

🥚입력/출력

---

🍳코드

n = int(input())
dptable = [0]*1001
dptable[1] = 1
dptable[2] = 3

for i in range(1, n+1):
    if dptable[i] != 0:
        continue
    dptable[i] = (dptable[i-1] + dptable[i-2]*2)%10007

print(dptable[n])

---

🧂아이디어

• 이코테 바닥 공사 문제와 같은 문제
• 처음 풀어보는 문제 유형이었는데, 나에게는 어려워서 각종 블로그를 참고했다! 생각보다 간단하게 풀 수 있었다. DP의 힘을 다시 느낄 수 있었던 문제
• 포스트들을 읽어보면서 내 나름대로 정리한 것이 위의 그림.
• DP로 풀 수 있는 문제라는 생각이 들면, 점화식을 만들 수 있게끔 사고를 바꿔보자.