백준 [11726]: 2×n 타일링

📌 백준 [11726]: 2×n 타일링

🔗 문제 링크

---

문제 설명 📄

2×n 크기의 직사각형을 1×2와 2×1 타일로 채우는 방법의 수를 구하시오.
결과를 10007로 나눈 나머지를 출력하시오.

---

문제 접근 방식 💡

• 동적 프로그래밍(DP)을 사용하여 타일 채우는 방법의 수를 계산.
• dp[i]를 2×i 크기의 직사각형을 채우는 방법의 수로 정의.
• 점화식:
  • dp[i] = dp[i-1] + dp[i-2]
• 초기값:
  • dp[1] = 1
  • dp[2] = 2

---

Solution 💻

n = int(input())

dp = [1] * n

for i in range(2, n):
    dp[i] = dp[i - 1] + dp[i - 2]

print(dp[-1])

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n)
  • 1부터 n까지 반복문을 통해 DP 배열을 채움.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(n)
  • dp 배열이 n 크기로 사용됨.

---

리팩토링 🛠️

n = int(input())

if n == 1:
    print(1)
else:
    prev1, prev2 = 1, 2

    for i in range(3, n + 1):
        prev1, prev2 = prev2, prev1 + prev2

    print(prev2)

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n)
  • 반복문으로 n번 계산.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(1)
  • 상수 크기의 변수만 사용.