99클럽 코테 스터디 19일차 TIL Count Sorted Vowel Strings

 

 

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

 

 

1. 문제 및 접근

 

1641. Count Sorted Vowel Strings

 

n이 주어지고, n의 length를 가진 주어진 a, e, i, o, u인 모음의 조합들을 사전순서로 정렬해서

총 몇개를 만들 수 있는 지 반환

 

 

ex

Input: n = 1

Output: 5

Explanation: The 5 sorted strings that consist of vowels only are ["a","e","i","o","u"]

 

 

Constraints:

1 <= n <= 50

 

 

dp 문제인데 aeiou라면 조합 문제인데 중복이 가능하니 중복 조합 ex)5H2 = n+r-1Cr = 6C2 = 15개

 

 

 

 

 

 

2. 풀이

 

public class countSortedVowelStrings정답 {

    // 모음 리스트
    private static char[] vowel = new char[] {'a', 'e', 'i', 'o', 'u'};

    public static void main(String[] args) {
        int n = 33;
        System.out.println(countVowelStrings(n));  // 예시 테스트
    }

    public static int countVowelStrings(int n) {
        // dp 배열 초기화
        int[][] dp = new int[n + 1][5];

        // 길이가 1인 경우 초기화
        for (int j = 0; j < 5; j++) {
            dp[1][j] = 1;
        }

        // DP 테이블 채우기
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < 5; j++) {
                dp[i][j] = 0;
                for (int k = j; k < 5; k++) {
                    dp[i][j] += dp[i - 1][k];
                }
            }
        }

        // 결과 계산
        int result = 0;
        for (int j = 0; j < 5; j++) {
            result += dp[n][j];
        }

        return result;
    }

 

 

전체풀이

 

 

 

2-1 dp 기저조건

 

 

 

 

for 문으로 해줘도 되지만, 직관적으로 다가가기 위해 하나씩 저장

 

 

 

 

2-2 dp 배열 채우기

 

 

 

1. 기저조건을 채워줬으니 i는 2부터 n개까지 반복인데,

 

 

 

2. i는 2를 기준,  j는 a를 기준으로 예를 들어보자면 숫자를 모음에 대치한다면 0, 1, 2, 3, 4가 a e i  o u

 

 

3.

 

2개의 단어를 붙일 "ae"는 j인 a일때, k = e인 경우 현재 수에 ij에 저장된 수에 전에 경우의 수를 하나씩 계속 더해주는 것이다.

 

"ae" 까지 모두 저장된 경우의 수는 사실  i가 하나일 때의 a + i + e + o + u  

 

 

즉 직전 갯수의 경우의 수를 j에게 다 합산해서 더해준다 !

 

 

 

2-3 count

 

 

 

각 저장된 수를 다 더해주면 모든 갯수 반환 가능!

 

3 마무리

 

 

 

진짜 dp는 악랄하다..

gpt가 풀어줘서 할 말이 없네 ㅠㅠ

 

내 머리의 한계를 느끼기 너무 쉬워서 반복적인 풀이로 문제의 규칙들을 아예 익숙하게 만드는 것이 베스트일 것 같다.

 

 

다시 생각해야할 것이 i j나 dp에 저장되는 값은 현재 수에 모든 경우의 수들이 저장된다 (max의 느낌으로 생각하자 무조건)

 

그리고 나는 바보다