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

뭐지?? 엄청 쉽게풀었다

근데 효율이 좋진 않아서 다른사람이 올린 코드를 참고해서 속도를 조금 더 늘려봤다.

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

---

문제는 간단했다.. 

순서대로 조합하는것 -> 순열!! 처음에는 식 하나로 해결하려고 했는데 그건 안될거같고

 

나는 재귀를 사용했다. 이전에 순열문제 풀었던거랑 비슷하게!

class Solution {
public:
    
    int check(int prefix, int n){
        if(n == 1){
            return prefix;
        }
        int result = 0;
        for(int i = prefix; i > 0; i--){
            result += check(i, n-1);
        }
        return result;
    }
    
    int countVowelStrings(int n) {
        
        int answer = check(5, n);
        
        return answer;
        
    }
};

-> 결과는 잘 나오는데 여러모로 느리고 메모리도 많이 잡아먹는다.

 

재귀가 아닌 while을 사용하면 이렇게된다.

class Solution {
public:
    
    
    
    int countVowelStrings(int n) {
        
        int u = 1; // 항상 1
        int o = 1; // u누적
        int i = 1; // o, u 누적
        int e = 1; // u, o, i 누적
        int a = 1; // u, o, i, e 누적
        
        while(n > 1){
            o += u;
            i += o;
            e += i;
            a += e;
            n--;
        }
        
        int answer = u + o + i + e + a;
        
        return answer;
        
    }
};

---

그래서 이번 문제는 어떤 알고리즘 쓰는거지,,?

파스칼의 삼각형을 이용하는거였다! 아하!