BOJ_11727 : 2×n 타일링 2

👉 문제링크

11727번: 2×n 타일링 2

---

---

🔸 문제 분석 🔸

• 1x2, 2x1, 2x2 타일을 채우는 경우의 수를 출력한다.
• 점화식은 dp[n] = dp[n-1] + dp[n-2]*2 이다.

🔸 코드 🔸

arr = [1,1]

for _ in range(int(input())-1):
    arr.append((arr[-1]+arr[-2]*2)%10007)

print(arr[-1])

🔸 코드 해석 🔸

• 리스트의 초기값을 1,1로 두고 점화식을 적용한다.
• 문제 조건에 따라 10007의 나머지로 계산한다.

---

🔸 end 🔸

• 2xn타일 1을 풀고 바로 2를 풀어보는 건데 점화식이 조금 달라진 것 말고는 비슷한 것 같다.
• 이번에도 dp문제를 그냥 경우의 수가 늘어나는 규칙을 찾아 코드로 변환했다.
  • 원리를 이해하는 방식으로 dp를 풀어야할 것 같아서 이번에는 풀이 포스팅을 찾아보았다.
  • 마지막 단에서 계산하니 금방 이해되는 방식이었다.
    • 마지막 칸에 1x2가 배치된다면 >> (n-1) 번째 칸까지의 경우의 수 : f(n-1)
    • 마지막 칸에 2x1 혹은 2x2가 배치된다면 >> (n-2) 번째 칸까지의 경우의 수x2 : f(n-2)*2