[LeetCode] 1641. Count Sorted Vowel Strings

[문제 링크]

https://leetcode.com/problems/count-sorted-vowel-strings/description/

 

[문제]

- 문제 설명
주어진 숫자 n에 대해, 길이가 n인 정렬된 모음 문자열의 개수를 구하는 문제입니다. 모음은 a, e, i, o, u 5개가 있습니다. 문자열은 알파벳 순서대로 정렬되어야 하며, 예를 들어 a는 e, i, o, u 앞에 올 수 있지만 그 반대는 안 됩니다.



- 입력
정수 n이 주어집니다. (1 ≤ n ≤ 50)



- 출력
길이가 n인 정렬된 모음 문자열의 개수를 반환해야 합니다.

[풀이 과정]

코드 주석으로 설명하겠습니다.

 

[코드]

class Solution {
    public int countVowelStrings(int n) {
        // dp[i]는 길이가 i인 문자열에서 i번째 모음으로 끝나는 문자열의 개수
        int[] dp = new int[5];
        // 길이가 1일 때, 각 모음으로 끝나는 문자열의 개수는 1
        Arrays.fill(dp, 1);

        // 길이 2부터 n까지 계산
        for (int i = 2; i <= n; i++) {
            // 현재 길이에 대한 새로운 dp 배열
            int[] newDp = new int[5];
            // 각 모음의 끝에서 누적합을 계산
            // 여기서 점화식인데 다음 배열의 첫번째 값은
            // 전에 전체 값을 더한 값이고
            // 그 이후 부턴 앞의 값을 하나씩 빼면 구해지는 문제
            newDp[0] = dp[0] + dp[1] + dp[2] + dp[3] + dp[4];
            newDp[1] = dp[1] + dp[2] + dp[3] + dp[4];
            newDp[2] = dp[2] + dp[3] + dp[4];
            newDp[3] = dp[3] + dp[4];
            newDp[4] = dp[4];
            
            dp = newDp;
        }

        // 최종 결과는 dp 배열에 저장된 값들의 합
        return dp[0] + dp[1] + dp[2] + dp[3] + dp[4];
    }
}

[회고]

항상 dp문제가 그렇지만 점화식을 찾기만하면 쉬운 것 같습니다.

 

 

 

 

질문과 피드백은 언제나 환영입니다.

감사합니다.