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

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

---

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

문제 설명:

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

---

문제 해결 코드

// 백준 11726 - 2×n 타일링
#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] = 2; // 2×2 직사각형을 채우는 방법은 2가지

    // 동적 프로그래밍
    for (int i = 3; i <= n; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % 10007;
    }

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

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명.

• 핵심 알고리즘:
  • 동적 프로그래밍(DP)을 사용하여 이전 단계의 결과를 바탕으로 새로운 결과를 계산합니다.
  • 점화식: dp[i] = (dp[i-1] + dp[i-2]) % 10007
• 구현 세부사항:
  • dp[1]과 dp[2]는 초기 조건으로 설정합니다.
  • dp[i]는 dp[i-1]과 dp[i-2]의 합을 10,007로 나눈 나머지를 저장합니다.
  • 결과를 출력하기 전에 나머지 연산을 수행하여 오버플로를 방지합니다.
• 시간 복잡도 분석:
  • 반복문: O(n)
  • 총 시간 복잡도: O(n)

---

결과

제출 시, 모든 테스트 케이스에 대해 올바른 결과를 출력합니다.

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