[백준 2922] 즐거운 단어 (C++)

문제 링크: www.acmicpc.net/problem/2922

2922번: 즐거운 단어

1. 주의할 점

- 정답은 Long Long 형태다

- 그리디한 방법으로 접근한다

- 모음↔L↔L이 아닌 자음 총 3가지의 경우를 두고 한다

 

2. 구현

- Dfs() 함수를 통해 시작하며, 매개변수로는 현재 index 번호, 연속된 모음의 수, 연속된 자음의 수, L의 여부, 현재까지의 형태로 진행될 수 있는 수가 차례대로 입력된다

- 입력받은 Str에 대해 모든 탐색이 끝났고, L이 있었다면 Result에 Cnt만큼 더해주고 리턴한다

- 현재 문자가 '_'일 때, 이번 칸에 모음이 들어올 수 있다면 모음 진행. 자음도 들어올 수 있다면, 자음도 진행한다. 단, L과 L을 포함하지 않는 자음으로 나눈다

- 현재 문자가 모음이며, 이전까지 연속된 모음이 2개가 아니라면 다음 문자로 진행한다

- 현재 문자가 자음이며, 이전까지 연속된 자음이 2개가 아니라면, 다음 문자로 진행한다. 단, 이때도 현재 문자가 L인지 L이 아닌 자음인지 구분한다

#include <iostream>
#include <string>
using namespace std;
long long result=0,len;
string str;

void dfs(int idx, int m, int j, bool l, long long cnt){
    if(idx==len){
        if(l)    result+=cnt;      
        return;
    }
    char c = str[idx];
    if(c=='_'){
        bool mavail=true;
        bool javail=true;
        if(m==2)  mavail=false;
        if(j==2) javail=false;
        if(mavail)  dfs(idx+1,m+1,0,l,cnt*5);
        if(javail){
            dfs(idx+1,0,j+1,true,cnt);
            dfs(idx+1,0,j+1,l,cnt*20);
        }
    }
    else if(c=='A' || c=='E' || c=='I' || c=='O' || c=='U'){
        if(m==2) return;
        dfs(idx+1,m+1,0,l,cnt);
    }
    else{
        if(j==2) return;
        if(c=='L') dfs(idx+1,0,j+1,true,cnt);
        else dfs(idx+1,0,j+1,l,cnt);
    }
}

int main() {
    cin>>str;
    len = str.size();
    dfs(0,0,0,false,1);
    cout<<result;
    return 0;
}