[PS][Swift][LeetCode] 1220. Count Vowels Permutation

문제

간단한 문제 정리

특정한 모음뒤에는 역시나 특정한 모음이 올수밖에 없는 구조입니다.

다시 생각해보면 어떤 모음에 대한 문자열에 대해 생각해 볼 때,
현재 a 알파벳이다 라고 한다면, a앞에는 e나 i만 올 수 있다는 얘기가 됩니다.

그렇다면 간단한 수식이 성립하는데 다음과 같습니다.

다이나믹 프로그래밍 수식이 너무 간단하게 성립해버려서.. 이 문제는 사실 Hard라고 표시되는게 맞는지 잘 모르겠어요

코드

import Foundation

class Solution {
    let INF = 1000000000 + 7
    var dp: [[Int]] = []
    func countVowelPermutation(_ n: Int) -> Int {
        dp = [[Int]](repeating: [Int](repeating: 0, count: 5), count: n + 2)
        for i in 0..<5 { dp[1][i] = 1 }
        
        for i in stride(from: 2, to: n + 1, by: 1) {
            dp[i][0] = (dp[i - 1][1] + dp[i - 1][4] + dp[i - 1][2]) % INF
            dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % INF
            dp[i][2] = (dp[i - 1][1] + dp[i - 1][3]) % INF
            dp[i][3] = dp[i - 1][2] % INF
            dp[i][4] = (dp[i - 1][3] + dp[i - 1][2]) % INF
        }
        
        return (dp[n][0] + dp[n][1] + dp[n][2] + dp[n][3] + dp[n][4]) % INF
    }
}

Insight

• 오늘은 없는거같습니다.