[BOJ / C++] 12037번 : Polynesiaglot (Small1)

문제 (Google 번역)

Ursula는 인공 언어 구성의 열렬한 팬입니다. 현재 그녀는 실제 폴리네시아어에서 영감을 받은 언어 작업을 시작하고 있습니다. 그녀가 정한 유일한 규칙은 다음과 같습니다.

• 모든 단어는 문자로 구성됩니다. 문자는 자음 또는 모음입니다.
• 단어의 모든 자음은 바로 뒤에 모음이 와야 합니다.

예를 들어, a  가 유일한 모음이고  h  가 유일한 자음  인 언어에서  a ,  aa ,  aha ,  aaha 및  haha  는 유효한 단어이지만  h ,  ahh ,  ahah 및  ahha  는 유효하지 않습니다. 자음에 관한 규칙은 단어가 자음으로 끝나는 것과 자음 뒤에 다른 자음이 오는 것을 허용하지 않는다는 점에 유의하세요.

Ursula의 새 언어에   사용할 수 있는  C  개의 다른 자음과  V 개의 다른 모음이 있는 경우,  그녀의 언어에는 길이가 L 인 유효한 단어가 몇 개 있습니까? 출력이 정말 큰 숫자가 될 수 있기 때문에 결과를 소수 10 9 +7(1000000007)로 나눈 나머지만 출력하도록 요청합니다.

입력

입력의 첫 번째 줄은 테스트 사례의 수  T를 제공합니다 . T  테스트 사례는 다음과 같습니다. 각각은 세 개의 정수 C ,  V 및  L 이 있는 한 줄로 구성됩니다  .

제한

• T  = 15.
• C  = 1.
• V  = 1.
• 1 ≤  L  ≤ 15.

출력

각 테스트 사례에 대해 다음을 포함하는 한 줄을 출력합니다  Case #x: y. 여기서  x 는 테스트 사례 번호(1부터 시작)이고 는   언어에서 길이가 Ly  인 서로 다른 유효한 단어의 수입니다(  modulo the prime 10 9 +7 (1000000007)).

Solved.ac 레벨

실버 V

풀이

음.... 일단 이 분의 블로그에서 이차원 배열을 활용해야 한다는 것, 시작하는 문자의 종류가 아닌 끝나는 문자의 종류를 이용해야 한다는 것을 알게 되어 많은 도움을 얻었다.

[C] 백준 | 12037번 코드 - Polynesiaglot

16 * 2 사이즈의 이차원 배열을 활용하여 모음으로 끝날 때, 자음으로 끝날 때로 나누어 생각해보자.

 

우선,

1. 모음으로 끝날 때는 앞에 자음과 모음 둘 다 올 수 있다. 

(ex : aa, ab)

2. 문자열이 자음으로 끝날 수가 없다. (자음 뒤에는 무조건 모음이 와야 하므로.)

 

입출력 예제에는 없지만 

c = 2, v = 2, l = 3 이고, 각각 자음과 모음은 이해하기 편하도록 b, c와 a, e로 생각해보자.

 

dp[1][0], 즉 문자열의 길이가 1이고 모음으로 끝나는 경우는 a, e 두 가지 경우의 수가 올 수 있다.

dp[1][0] = v

dp[1][1], 즉 문자열의 길이가 1이고 자음으로 끝나는 경우는 있을 수 없다.

dp[1][1] = 0

처음으로 dp 배열은 위와 같이 초기화를 해두고 문자열의 길이가 2일 때부터 생각해볼 수 있다.

대충 내가 문제를 해결한 과정을 필기로 나타냈는데 나 외에는 이해가 어려워보인다. 차근차근 설명해드리겠습니다 꾸벅

 

편의상 필기에서는 모음으로 끝나고 바로 앞에 자음이 왔을 때, 모음이 왔을 때로 구분지어 작성해보았다.

왼쪽부터 차근차근 설명을 해보자면

 

dp[1][0]이 2라는 점은 위에서 설명을 했고,

a와 e로 끝났을 시 각각 b와 c가 앞에 올 수 있고 이때 경우의 수는 각각 2개씩 해서 4, 그리고 이것은 dp[2][1]을 구한 것이다.

dp[2][1] = dp[1][0] (모음으로 끝난 경우의 수) * c (자음의 개수)로 나타낼 수 있다.

이후로 dp[3][1]에는 모음만 올 수 있으므로 다시 dp[2][0] * c로 나타낼 수 있고 이를 구하는 과정은 오른쪽 부분에 있다.

 

오른쪽을 설명해보자면

dp[2][0], 즉 문자열이 모음으로 끝나고 다시 모음이 오는 경우의 수는 직전 경우의 모음이 오는 경우의 개수 * 모음의 개수다.

식은 dp[2][0] = dp[1][0] * 2 + dp[1][1] * 2로 적어두었는데 이는 dp[3][0]을 구하는 과정에서 설명이 가능하다.

모음으로 끝난 경우 그 앞에는 자음과 모음이 둘 다 올 수 있기 때문에 자음이 오는 경우의 수를 더해주는 것이다.

 

음, 설명을 잘 한지 모르겠다. 일단은 내가 이해한 바를 남들도 이해할 수 있게 전달하는게 너무 힘드네...

어쨌든 위와 같은 과정을 거친 후 내가 도출해낸 점화식은 다음과 같다.

 

1. 모음으로 끝났을 때 (자음과 모음이 모두 올 수 있음)
dp[i][0] = dp[i - 1][0] * v + dp[i - 1][1] * v

2. 자음으로 끝났을 때 (모음만 올 수 있음)
dp[i][1] = dp[i - 1][0] * c

길이가 l일 때의 경우의 수는 dp[l][0] + dp[l][1]이다.

문제 조건에서 10 ^ 9 + 1로 나눈 나머지를 출력하라는 것을 잊지 말자

Code

#include<bits/stdc++.h>
#define res 1000000007

using namespace std;

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

    int t;
    cin >> t;

    for(int i = 1; i <= t; i++) {
        int c, v, l;
        int dp[16][2];

        for(int j = 1; j <= 16; j++) {
            for(int k = 0; k < 2; k++) {
                dp[j][k] = 0;
            }
        }

        cin >> c >> v >> l;

        dp[1][0] = v;
        dp[1][1] = 0;

        for(int j = 2; j <= l; j++) {
            dp[j][0] = (dp[j - 1][0] * v) + (dp[j - 1][1] * v) % res;
            dp[j][1] = c * dp[j - 1][0] % res;
        }

        cout << "Case #" << i << ": " << (dp[l][0] + dp[l][1]) % res << "\n";
    }

    return 0;
}

아 내가 이해하고 푸는 과정도 오래걸리고 설명하기 위한 과정도 오래걸렸는데 사실 내가 설명을 잘 한지도....모르겠다.

 

12037번: Polynesiaglot (Small1)