[이코테] DP : 바닥 공사

문제

1X2, 2X1, 2X2 크기의 덮개가 있을 때 2XN의 바닥을 모두 채우는 경우의 수를 구하는 문제이다.

✍️ 나의 풀이

---

• 가로 1칸으로 채울 수 있는 수는 1개이다.
• 가로 2칸으로 채울 수 있는 수는 3개이나 가로 1칸을 2개 쓴 것과 겹치므로 2개이다.

따라서, 점화식은 d[n] = d[n-1] + 2 * d[n-2]이다.

🛠 나의 코드

---

n = int(input())
d = [0]*(n+1)
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[n])

📝 정리

---

🎈 참고

---

• 이것이 취업을 위한 코딩테스트다 with python