백준 12037번: Polynesiaglot (Small1) (C++)

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

12037번: Polynesiaglot (Small1)

---

Solved By: DP

 

cache[i][0]: 모음으로 끝나는 길이가 i인 문자열의 개수

cache[i][0]: 자음으로 끝나는 길이가 i인 문자열의 개수

 

다음과 같이 세팅하고 DP를 돌렸습니다.

#include <iostream>
#define MAX 16
using namespace std;

int cache[MAX][2];
const int mod = 1000000007;

int main(){
    int T; cin >> T;
    int cnt = 1;
    while(T--){
        int c, v, l; cin >> c >> v >> l;
        cache[1][0] = v;
        cache[1][1] = c;
        for(int i = 2; i <= l; i++){
            cache[i][0] = ((v % mod) * ((cache[i - 1][0] % mod + cache[i - 1][1] % mod) % mod)) % mod;
            cache[i][1] = ((c % mod) * (cache[i - 1][0] % mod)) % mod;
        }
        cout << "Case #" << cnt << ": ";
        cout << cache[l][0] << '\n';
        cnt++;
    }
}