[BOJ] 11726 2xn 타일링

📌 문제 제목

문제 링크: BOJ 11726

---

🗒️ 문제 설명

2xn 크기의 직사각형을 1x2, 2x1 타일로 채우는 방법의 수를 구하는 프로그램

2xn 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력

시간 제한: 1초

메모리 제한: 256MB

1 <= n <= 1,000

---

💡 문제 해결 아이디어

• 테이블 정의
  • dp[i]는 2xi 크기의 직사각형을 채우는 방법의 수
• 점화식 찾기
  • 2xi 크기의 직사각형이 있을 때, 왼쪽 위를 2x1 크기의 직사각형으로 채우는 경우
  • 2xi 크기의 직사각형이 있을 때, 왼쪽 위를 1x2 크기의 직사각형으로 채우는 경우
  • ※ dp[i] = dp[i-1] + dp[i-2]
• 초기값 정하기
  • dp[1] = 1, dp[2] = 2

---

⌛️ 시간 복잡도

• O(N)

---

✅ 최종 코드

import sys
input = sys.stdin.readline

n = int(input().strip())

if n == 1:
    print(1)
elif n == 2:
    print(2)
else:
    dp = [-1] * (n+1)
    dp[1] = 1
    dp[2] = 2

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

    print(dp[n])

# 공간복잡도를 O(1)로 줄일 수 있다.

import sys
input = sys.stdin.readline

n = int(input().strip())

if n == 1:
    print(1)
elif n == 2:
    print(2)
else:
    a, b = 1, 2  # a = dp[i-2], b = dp[i-1]
    for _ in range(3, n + 1):
        a, b = b, (a + b) % 10_007
    print(b)