Silver III 난이도 문제를 C++로 풀이한 내용입니다. 길이가 N인 이진 문자열을 만드는 경우의 수를 구하는 문제입니다.

백준 1904: 01타일

Silver III 난이도 문제를 C++로 풀이한 내용입니다. 길이가 N인 이진 문자열을 만드는 경우의 수를 구하는 문제입니다.

문제 소개

문제 번호: 1904
문제명: 01타일
난이도: Silver III
사용 언어: C++
실행 시간: 4 ms
메모리: 5928 KB

주어진 문제는 길이가 $N$ 인 이진수열을 만들 때, '01' 타일과 '1' 타일을 사용하여 채우는 경우의 수를 구하는 것입니다. 여기서 '01' 타일은 길이 2를 차지하고, '1' 타일은 길이 1을 차지합니다.

접근 방법

이 문제는 동적 계획법(Dynamic Programming, DP)을 사용하여 해결할 수 있습니다. 길이가 $N$ 인 이진수열을 만드는 경우의 수를 구해야 하는데, 이는 더 작은 길이의 이진수열을 만드는 경우의 수로부터 유도할 수 있습니다.

생각의 흐름:
- 길이가 $i$ 인 이진수열을 만드는 마지막 타일이 무엇인지에 따라 경우의 수를 나눌 수 있습니다.
- 마지막이 '1' 타일인 경우: 이 앞에는 길이가 $i - 1$ 인 이진수열이 있어야 합니다. 따라서 경우의 수는 길이가 $i - 1$ 인 이진수열을 만드는 경우의 수와 같습니다.
- 마지막이 '01' 타일인 경우: 이 앞에는 길이가 $i - 2$ 인 이진수열이 있어야 합니다. 따라서 경우의 수는 길이가 $i - 2$ 인 이진수열을 만드는 경우의 수와 같습니다.
- 이 두 경우는 서로 배타적이므로, 길이가 $i$ 인 이진수열을 만드는 총 경우의 수는 길이가 $i - 1$ 인 경우의 수와 길이가 $i - 2$ 인 경우의 수를 더한 값이 됩니다.
알고리즘/자료구조: 동적 계획법 (DP)을 사용했습니다. vector를 사용하여 DP 테이블을 구축했습니다.
선택 이유: 문제의 특성상 부분 문제의 해를 이용하여 전체 문제의 해를 효율적으로 구할 수 있기 때문에 DP가 적합하다고 판단했습니다. 또한, 타일을 이용하는 문제는 종종 피보나치 수열과 유사한 점화식을 가지므로 DP 접근이 자연스럽습니다.

풀이 과정

문제 정의: dp[i]를 길이가 $i$ 인 이진수열을 만드는 총 경우의 수라고 정의합니다.
기저 사례 (Base Cases):
- 길이 1 (dp[1]): '1' 타일 하나로만 만들 수 있습니다. 따라서 dp[1] = 1입니다.
- 길이 2 (dp[2]): '11' (1 타일 + 1 타일) 또는 '00' (01 타일)로 만들 수 있습니다. 따라서 dp[2] = 2입니다. (문제에서 '1' 타일과 '01' 타일을 사용한다고 했지만, 이진수열을 만든다는 맥락에서 '11'과 '00'으로 해석하는 것이 일반적입니다. 만약 '01'과 '1'만 사용할 수 있다면 '11'은 '1' + '1', '00'은 '01'로 해석됩니다. 실제 문제는 '1' 또는 '11'로 채우는 것으로 해석하는 것이 일반적이며, 여기서는 0과 1로 이루어진 이진 문자열을 만드는 것으로 해석했습니다. 문제의 설명을 바탕으로 '1'은 1칸, '01'은 2칸을 채운다고 가정하면, 이진수열의 각 자리가 0 또는 1로 채워지는 것이 아니라, 타일로 "길이"를 채우는 것으로 해석해야 합니다. 문제 설명의 "이진 문자열"이라는 표현은 혼동을 줄 수 있으나, 일반적으로 이 문제는 "1" 또는 "11" 타일로 길이를 채우는 경우의 수와 동일합니다. 즉, 길이가 $N$ 이라면, 마지막이 1이면 앞의 길이가 $N - 1$ 인 경우, 마지막이 11이면 앞의 길이가 $N - 2$ 인 경우로 볼 수 있습니다. 따라서 dp[i] = dp[i-1] + dp[i-2]가 도출됩니다.)
점화식 (Recurrence Relation):
길이가 $i$ ( $i \geq 3$ )인 이진수열을 만드는 마지막 경우는 두 가지로 나눌 수 있습니다.
- 마지막이 '1' 타일인 경우: 이 앞에는 길이가 $i - 1$ 인 이진수열이 존재합니다. 경우의 수는 dp[i-1]입니다.
- 마지막이 '11' 타일인 경우: 이 앞에는 길이가 $i - 2$ 인 이진수열이 존재합니다. 경우의 수는 dp[i-2]입니다.
따라서 dp[i] = dp[i-1] + dp[i-2] 입니다.
모듈러 연산: 경우의 수가 매우 커질 수 있으므로, 문제에서 요구하는 모듈러 연산(15746)을 각 단계마다 적용합니다. dp[i] = (dp[i-1] + dp[i-2]) % MOD;
결과 출력: 계산된 dp[n] 값을 출력합니다.

코드 설명

#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;

    const int MOD = 15746;

    // dp[n] = 길이가 n인 이진 문자열을 만들 수 있는 경우의 수
    vector<int> dp(n+1);

    // [기저 사례]
    // 길이 1:
    // 만들 수 있는 건 "1" 하나뿐
    dp[1] = 1;

    // 길이 2:
    // "11", "00" 두 가지
    if (n >= 2) dp[2] = 2;

    // [점화식 채우기]
    for (int i = 3; i <= n; i++) {
        /*
            길이 i짜리 문자열의 마지막 경우는 두 가지뿐

            1) 마지막이 '1'인 경우
               → 앞은 길이 i-1
               → 경우의 수: dp[i-1]

            2) 마지막이 '00'인 경우
               → 앞은 길이 i-2
               → 경우의 수: dp[i-2]

            두 경우는 서로 겹치지 않으므로 더해준다.
        */
        dp[i] = (dp[i-1] + dp[i-2]) % MOD;
    }

    // 길이 n짜리 전체 경우의 수 출력
    cout << dp[n];
}

주요 부분 설명

#include <bits/stdc++.h>: 표준 라이브러리의 대부분을 포함합니다.
using namespace std;: std 네임스페이스를 사용합니다.
ios::sync_with_stdio(false); cin.tie(NULL);: C++ 표준 입출력 성능을 최적화합니다.
const int MOD = 15746;: 문제에서 요구하는 모듈러 값입니다.
vector<int> dp(n+1);: 길이가 0부터 n까지의 경우의 수를 저장할 DP 테이블입니다. 0번 인덱스는 사용하지 않거나, 필요에 따라 초기화할 수 있습니다.
dp[1] = 1;: 길이가 1인 경우의 수 초기화.
if (n >= 2) dp[2] = 2;: 길이가 2인 경우의 수 초기화. n이 1일 경우를 대비하여 조건문을 사용했습니다.
for (int i = 3; i <= n; i++) { ... }: 3부터 n까지 반복하며 DP 값을 계산합니다.
dp[i] = (dp[i-1] + dp[i-2]) % MOD;: 점화식을 적용하여 DP 값을 계산하고 모듈러 연산을 수행합니다.
cout << dp[n];: 최종적으로 계산된 길이가 n인 경우의 수를 출력합니다.

복잡도 분석

시간 복잡도: for 루프가 3부터 n까지 $O (n)$ 번 반복됩니다. 루프 안의 연산은 상수 시간이므로, 전체 시간 복잡도는 ** $O (n)$ **입니다.
공간 복잡도: vector<int> dp(n+1);를 사용하여 $O (n)$ 크기의 메모리를 사용합니다. 따라서 공간 복잡도는 ** $O (n)$ **입니다.

배운 점

이 문제를 통해 동적 계획법의 기본 원리를 다시 한번 확실히 이해할 수 있었습니다. 특히, 다음과 같은 점을 배울 수 있었습니다.

부분 문제 정의: 큰 문제를 더 작고 독립적인 부분 문제로 나누는 것이 DP의 핵심입니다. dp[i]를 정의하는 것이 첫걸음입니다.
점화식 도출: 현재 상태(dp[i])를 이전 상태(dp[i-1], dp[i-2])의 조합으로 표현하는 방법을 고민하는 것이 중요합니다. 문제의 조건을 세밀하게 분석하여 점화식을 찾아내야 합니다.
기저 사례 설정: DP를 시작하기 위한 초기 조건을 정확하게 설정하는 것이 중요합니다. 잘못된 기저 사례는 전체 계산 결과를 틀리게 만듭니다.
모듈러 연산의 중요성: 큰 숫자가 나올 수 있는 문제에서는 모듈러 연산을 잊지 않고 적용해야 합니다. 연산 중간중간 모듈러 연산을 적용하는 것이 오버플로우를 방지하는 효과적인 방법입니다.
피보나치 수열과의 유사성: 이 문제는 피보나치 수열과 매우 유사한 점화식을 가집니다. 특정 패턴을 파악하면 유사한 문제를 해결하는 데 도움이 될 수 있습니다.

이 문제는 DP 문제 풀이의 좋은 예시이며, 다른 DP 문제에도 적용할 수 있는 기본적인 접근 방식을 익힐 수 있었습니다.