[LeetCode] 1220. Count Vowels Permutation

https://leetcode.com/problems/count-vowels-permutation/description/

Count Vowels Permutation - LeetCode

leetcode - Count Vowels Permutation

문제 유형: 재귀, 다이나믹 프로그래밍

문제 난이도: Hard

 

문제

Given an integer n, your task is to count how many strings of length n can be formed under the following rules:

• Each character is a lower case vowel ('a', 'e', 'i', 'o', 'u')
• Each vowel 'a' may only be followed by an 'e'.
• Each vowel 'e' may only be followed by an 'a' or an 'i'.
• Each vowel 'i' may not be followed by another 'i'.
• Each vowel 'o' may only be followed by an 'i' or a 'u'.
• Each vowel 'u' may only be followed by an 'a'.

Since the answer may be too large, return it modulo 10^9 + 7.

 

정수 n이 주어집니다. 아래 규칙을 따르는 n만큼의 길이의 문자열의 경우의 수를 구하시오.

- 각 문자는 소문자 모음입니다. ('a', 'e', 'i', 'o', 'u')

- 'a' 다음에는 'e'만 붙을 수 있습니다.

- 'e' 다음에는 'a'나 'i'만 붙을 수 있습니다.

- 'i' 다음에는 'i'가 올 수 없습니다.

- 'o' 다음에는 'i'나 'u'만 붙을 수 있습니다.

- 'u' 다음에는 'a'만 붙을 수 있습니다.

 

값이 커질 수 있으니, 1e9+7로 나누시오.

 

풀이

dp배열을[남은 길이][현재 문자]로 초기화합니다.

남은 길이가 0이라면, 문자열을 완성했다는 뜻으로, 1을 반환합니다.

만약 dp에 값이 있다면, 그 값을 반환합니다.

아니라면, 현재 문자 다음에 올 문자 후보들을 재귀적으로 계산하여 누적시킨 값을 dp에 저장시키고 반환합니다.

위 과정을 a, e, i, o, u로 시작하는 경우마다 각각 누적시킵니다.

 

1e9+7로 나눠야 하는 것을 유의해서 누적시켜야 합니다.

 

코드

C++

class Solution {
public:
    const int MOD = 1e9+7;

    unordered_map<int, vector<int>> followers {
        {0, {1}},
        {1, {0, 2}},
        {2, {0, 1, 3, 4}},
        {3, {2, 4}},
        {4, {0}}
    };

    int dp[20001][5];

    Solution() {
        dp[0][0] = 1;
        dp[0][1] = 1;
        dp[0][2] = 1;
        dp[0][3] = 1; 
        dp[0][4] = 1;
    }

    int solve(int remain, int prefix) {
        if (remain <= 0) return 1;
        int& result = dp[remain][prefix];
        if (result != -1) return result;

        vector<int> nextVowels = followers[prefix];
        int sum = 0;
        for (const auto& next : nextVowels) {
            sum = (sum + solve(remain-1, next)) % MOD;
        }
        return result = sum;
    }

    int countVowelPermutation(int n) {
        int sum = 0;
        memset(dp, -1, sizeof(dp));
        for (int i = 0; i < 5; i++) {
            sum = (sum + solve(n-1, i)) % MOD;
        }

        return sum;
    }
};