백준 [1309]: 동물원

📌 백준 [1309]: 동물원

🔗 문제 링크

---

문제 설명 📄

가로의 길이가 2이고 세로의 길이가 N인 우리에 사자를 배치하려 한다.
사자는 가로로 붙어있는 두 칸에 함께 있을 수 없다.
우리에 사자를 배치하는 방법의 수를 9901로 나눈 나머지를 구하시오.

---

문제 접근 방식 💡

• 동적 프로그래밍(DP)을 사용하여 사자를 배치하는 경우의 수를 계산.
• 세 가지 경우를 고려:
  1. 사자를 왼쪽 칸에 배치 (b)
  2. 사자를 오른쪽 칸에 배치 (c)
  3. 사자를 배치하지 않음 (a)
• 점화식:
  • a(n) = a(n-1) + b(n-1) + c(n-1) (배치하지 않는 경우)
  • b(n) = a(n-1) + c(n-1) (왼쪽에 배치)
  • c(n) = a(n-1) + b(n-1) (오른쪽에 배치)
• 최종 답은 a + b + c

---

Solution 💻

n = int(input())
MOD = 9901

a, b, c = 1, 1, 1 

for _ in range(2, n + 1):
    a, b, c = (a + b + c), (a + c), (a + b)

print((a + b + c) % MOD)

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n)
  • n번의 반복문을 통해 경우의 수를 누적.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(1)
  • 상수 크기의 변수만 사용하여 메모리 절약.