1220. Count Vowels Permutation

• 조합을 생성하는 규칙으로 부터 경우의 수를 구하는 문제.

• 첫번째부터 시작하여 특정 index에 a, e, i, o, u 각 글자가 올 수 있는 경우의 수를 계산해나가면 된다.
• 이를 위해서 경우의 수를 세는 array curr, next를 만든다.
• 이전 경우의 수와 다음 경우의 수를 계산해 나가면서 swap을 수행해나간다.

• 먼저 첫번째 글자는 모든 글자가 고르게 올 수 있다. 따라서 맨 첫글자의 경우의 수는 각각 1개씩 인 것이 된다.
• vector<long long> curr(5, 1);

• 다음 index 부터는 이전에 온 글자에 따라서 경우의 수가 정해진다.
• 현재 index의 글자가 a 이려면 이전 글자가 e 여야 한다.
• 따라서 현재 index의 글자가 a 인 경우의 수 = 이전 글자가 e 인 경우의 수가 된다.
• 현재 index의 글자가 e 이려면 이전 글자가 a 또는 i 여야 한다.
• 따라서 현재 index의 글자가 e 인 경우의 수 = 이전 글자가 a 또는 i 인 경우의 수의 합이 된다.
• 현재 index의 글자가 i 이려면 이전 글자가 i 가 아닌 모든 글자 (a, e, o, u) 중 하나여야 한다.
• 따라서 현재 index의 글자가 i 인 경우의 수 = 이전 글자가 a, e, o, u 인 경우의 수의 합이 된다.
• 현재 index의 글자가 o 이려면 이전 글자가 i 또는 u 여야 한다.
• 따라서 현재 index의 글자가 o 인 경우의 수 = 이전 글자가 i 또는 u 인 경우의 수의 합이 된다.
• 현재 index의 글자가 u 이려면 이전 글자가 a 여야 한다.
• 따라서 현재 index의 글자가 u 인 경우의 수 = 이전 글자가 a 인 경우의 수가 된다.

• 이렇게 마지막 index까지 계산을 마치면 array curr 에는 마지막 index의 글자가 각각 a, e, i, o, u 인 경우의 수가 들어있다. 이 값을 모두 더하면 원하는 결과를 얻을 수 있다.

// a <- e 
// e <- ai
// i <- aeou
// o <- iu
// u <- a
class Solution {
public:
    static constexpr int MOD = 1e9 + 7;
    int countVowelPermutation(int n) {
        vector<long long> curr(5, 1);
        vector<long long> next(5, 0);
        while (--n > 0) {
            next[0] = curr[1];
            next[1] = (curr[0] + curr[2]) % MOD;
            next[2] = (curr[0] + curr[1] + curr[3] + curr[4]) % MOD;
            next[3] = (curr[2] + curr[4]) % MOD;
            next[4] = curr[0];
            curr.swap(next);
        }
        long long result = 0;
        for (auto v : curr) {
            result = (result + v) % MOD;
        }
        return result;
    }
};