Today's Challenge

fabichoi 2022. 8. 7. 23:45

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

Count Vowels Permutation - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

DP 문제임을 직감했으나.. 역시 N이 커서 솔루션 참고 ㅠ_ㅠ
dp[i][j]가 오직 dp[i-1][j]에 대해서만 의존적이어서 아래와 같이 짤 수 있음.

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        mod = math.pow(10, 9) + 7
        a, e, i, o, u = [1, 1, 1, 1, 1]
        for _ in range(n-1):
            a, e, i, o, u = map(lambda x: x % mod, [(e+i+u), (a+i), (e+o), (i), (i+o)])
        return int((a + e + i + o + u) % mod)