백준 1904번 [01타일](C++) -yes6686- 티스토리

백준 문제 풀이: 1904 [01타일]

---

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

문제 설명:

길이가 N인 01 타일로 이루어진 모든 가능한 이진 문자열의 개수를 구하는 문제입니다. 타일은 1×2와 2×1의 블록으로 구성되며, 다음 규칙을 따릅니다:

• N개의 타일은 1과 0으로 이루어진 이진 문자열로 표현됩니다.
• 길이가 1일 때는 "1", 길이가 2일 때는 "00" 또는 "11"입니다.
• 결과는 15746으로 나눈 나머지를 출력합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int dp[1000001]; // dp[i]: 길이가 i인 01 타일의 경우의 수

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n; // 타일의 길이
    cin >> n;

    // 초기값 설정
    dp[1] = 1; // "1"
    dp[2] = 2; // "00", "11"

    // 동적 프로그래밍으로 모든 경우의 수 계산
    for (int i = 3; i <= n; i++) {
        dp[i] = (dp[i - 1] + dp[i - 2]) % 15746;
    }

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

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 동적 프로그래밍을 사용하여 피보나치 수열의 변형 문제를 해결합니다. 길이가 N인 경우, N-1과 N-2 길이의 타일에서 새로운 타일을 추가하는 방식으로 문제를 풉니다.
• 구현 세부사항:
  • dp[i]: 길이가 i인 01 타일의 경우의 수를 저장합니다.
  • 점화식: dp[i] = (dp[i - 1] + dp[i - 2]) % 15746
  • 결과를 매번 15746으로 나눈 나머지를 저장하여 오버플로우를 방지합니다.
• 시간 복잡도 분석: O(N)
  • 배열을 한 번 순회하며 모든 경우의 수를 계산합니다.

---

결과

길이가 N인 01 타일의 경우의 수를 정확히 계산하고 15746으로 나눈 나머지를 출력합니다. 동적 프로그래밍을 사용하여 효율적으로 해결할 수 있습니다.

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