99클럽 코테 스터디 19일차 TIL + Math/Dynamic Programming/Combinatorics : count-sorted-vowel-strings

문제

링크텍스트

풀이

class Solution:
    def countVowelStrings(self, n: int) -> int:
        if n == 1:
            return 5
        def count(n,lc):
            if n == 2:
                return lc+1
            cnt = 0
            for i in range(lc+1):
                cnt += count(n-1,i)
            return cnt
        cnt = 0
        for i in range(5):
            cnt += count(n,i)
        return cnt

• 뒤의 문자는 앞의 문자보다 같거나 더 lexicographically 뒤에 있어야 합니다.
• 주어진 힌트 2에 따라 재귀 함수 count(n,lc)를 구성합니다.
  - 5개의 모음을 다음과 같이 정수로 가정하였습니다.
  - a:0, e:1, i:2, o:3, u:4
  - 마지막 문자 lc가 주어지는 경우에, n개의 문자열을 구성할 수 있는 경우의 수를 구합니다.
  • 종료조건으로 n == 2 인 경우에는 마지막 문자에 따라 경우의 수가 lc+1로 정해집니다.

결과