[Silver V] Polynesiaglot (Small1) - 12037

[문제 위치]

https://www.acmicpc.net/problem/12037

[문제 풀이]

이 문제는 문자열의 개수를 세는 문제이다.

길이가 L인 문자열을 만들 때, 모음은 어느 위치에나 올 수 있지만 자음은 반드시 바로 앞 문자가 모음일 때만 올 수 있다. 즉 자음이 연속으로 등장하는 경우는 허용되지 않는다. 또한 최종적으로 유효한 문자열은 반드시 모음으로 끝나야 한다.

이를 해결하기 위해 동적 계획법을 사용한다. 문자열의 길이와 마지막 문자의 종류에 따라 경우의 수를 나눈다. 길이 i에서 마지막 문자가 모음인 경우와 자음인 경우를 각각 따로 관리한다.

길이 i이고 모음으로 끝나는 경우의 수를 dpV[i], 자음으로 끝나는 경우의 수를 dpC[i]라고 정의한다.

모음으로 끝나는 경우는 이전 상태가 모음이든 자음이든 상관없이 모음을 하나 붙일 수 있으므로, dpV[i]는 dpV[i-1]과 dpC[i-1]의 합에 모음의 개수 V를 곱한 값이 된다.

자음으로 끝나는 경우는 바로 앞 문자가 반드시 모음이어야 하므로, dpC[i]는 dpV[i-1]에 자음의 개수 C를 곱한 값이 된다.

초기 상태로 길이 1일 때는 모음 하나로 끝나는 경우가 V가지, 자음 하나로 끝나는 경우가 C가지이다.

문제에서 요구하는 정답은 길이 L인 문자열 중 모음으로 끝나는 경우의 수이므로 dpV[L]이 된다. 모든 계산은 값이 매우 커질 수 있으므로 1,000,000,007로 나눈 나머지를 사용한다.

 

아래는 이를 구현한 코드이다.

#include <iostream>
#include <vector>

using namespace std;

#define FASTIO ios::sync_with_stdio(false); cin.tie(nullptr);

static const long long MOD = 1000000007LL;

int main() {
    FASTIO

        int T;
    cin >> T;

    for (int tc = 1; tc <= T; tc++) {
        long long C, V;
        int L;
        cin >> C >> V >> L;

        long long dpV = V % MOD; // 길이 1, 모음으로 끝
        long long dpC = C % MOD; // 길이 1, 자음으로 끝

        for (int i = 2; i <= L; i++) {
            long long nextV = ((dpV + dpC) % MOD) * (V % MOD) % MOD;
            long long nextC = (dpV % MOD) * (C % MOD) % MOD;
            dpV = nextV;
            dpC = nextC;
        }

        cout << "Case #" << tc << ": " << dpV % MOD << "\n";
    }

    return 0;
}