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

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

🔗 문제 링크

---

문제 설명 📄

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

---

문제 접근 방식 💡

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

---

Solution 💻

n = int(input())

dp = [0] * (n + 1)

if n == 1:
    print(1)
elif n == 2:
    print(3)
else:
    dp[1] = 1
    dp[2] = 3

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

    print(dp[-1] % 10007)

시간 복잡도 분석 ⏲️

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

공간 복잡도 분석 🗄️

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

---

리팩토링 🛠️

n = int(input())

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

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

    print(prev2 % 10007)

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(n)
  • 1부터 n까지의 반복문을 통해 계산.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(1)
  • 상수 크기의 변수를 사용하여 공간 최적화.