백준 11727번 [2×n 타일링 2](C++) -yes6686- 티스토리

백준 문제 풀이: 11727 [2×n 타일링 2]

---

문제 링크: https://www.acmicpc.net/problem/11727

문제 설명:

2×n 크기의 직사각형을 1×2, 2×1, 2×2 크기의 타일로 채우는 방법의 수를 구하는 문제입니다. 방법의 수는 10,007로 나눈 나머지를 출력합니다.

입력:

• 첫째 줄에 n이 주어집니다. (1 ≤ n ≤ 1,000)

출력:

• 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력합니다.

예시:

입력:
2

출력:
3

---

문제 해결 코드

#include <iostream>
using namespace std;

int dp[1001]; // dp[i]: 2×i 크기의 직사각형을 채우는 방법의 수

int main() {
    int n;
    cin >> n;

    dp[1] = 1; // 2×1 크기: 1가지 방법
    dp[2] = 3; // 2×2 크기: 3가지 방법

    for (int i = 3; i <= n; i++) {
        dp[i] = (dp[i - 1] + 2 * dp[i - 2]) % 10007;
    }

    cout << dp[n] << '\n'; // 결과 출력
    return 0;
}

---

코드 설명

이 코드는 동적 프로그래밍(DP)을 사용하여 문제를 해결합니다. 주요 로직과 알고리즘은 다음과 같습니다:

• 핵심 알고리즘:
  • 2×i 크기의 직사각형을 채우는 방법의 수를 dp[i]에 저장합니다.
  • 점화식: dp[i] = dp[i-1] + 2×dp[i-2]
  • 점화식 유도:
    • 2×(i-1) 크기의 직사각형에서 1×2 타일 하나를 추가하는 경우: dp[i-1]
    • 2×(i-2) 크기의 직사각형에서 2×2 또는 1×2 타일 2개를 추가하는 경우: 2×dp[i-2]
• 구현 세부사항:
  • dp 배열은 나머지 연산 % 10007을 통해 값을 저장하여 오버플로우를 방지합니다.
• 시간 복잡도 분석:
  • 점화식 계산: O(n)
  • 전체 시간 복잡도: O(n)

---

결과

코드는 입력된 n에 대해 2×n 크기의 직사각형을 채우는 방법의 수를 계산합니다. 동적 프로그래밍을 사용하여 효율적으로 문제를 해결하며, O(n)의 시간 복잡도로 대규모 입력도 처리할 수 있습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!