(C++) - 백준(BOJ) 2922 : 즐거운 단어

https://www.acmicpc.net/problem/2922

2922번: 즐거운 단어

brute force 문제였습니다.

 

📕 풀이방법

📔 입력 및 초기화

s를 입력받고 그 단어의 길이를 sSize에 저장합니다.

 

📔 풀이과정

밑줄의 개수는 최대 10개이기 때문에 재귀 형태로 backtracking함으로써 풀 수 있습니다.

 

 1. 기저 case는 모음 또는 자음의 개수가 3이상인경우 0을 반환하게 합니다. depth == sSize라면 l존재 여부를 반환합니다.

 

 2. s[depth]가 밑줄이라면 3가지의 경우가 존재합니다.

  2-1. l을 사용하는 경우

  2-2. l과 모음을 제외한 나머지 20개 알파벳을 사용하는 경우

  2-3. 모음을 사용하는 경우입니다.

 

 3. 밑줄이 아니라면 상황에 따라 재귀를 적절히 호출해줍니다.

📔 정답출력

backtracking함수의 결과값을 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
string s;
int sSize;
ll backtracking(ll depth, ll ja, ll mo, ll lexist){
    if(mo >= 3 || ja >= 3) return 0;
    if(depth == sSize) return lexist;
    ll ret = 0;
    if(s[depth] == '_'){
        ret += backtracking(depth + 1, ja + 1, 0, lexist) * 20;
        ret += backtracking(depth + 1, ja + 1, 0, 1);
        ret += backtracking(depth + 1, 0, mo + 1, lexist) * 5;
    }
    else {
        if(s[depth] == 'A' || s[depth] == 'E' || s[depth] == 'I' || s[depth] == 'O' || s[depth] == 'U')
            ret += backtracking(depth + 1, 0, mo + 1, lexist);
        else {
            if(s[depth] == 'L') ret += backtracking(depth + 1, ja + 1, 0, 1);
            else ret += backtracking(depth + 1, ja + 1, 0, lexist);
        }
    }
    return ret;
}
int main(){
    cin >> s;
    sSize = s.size();
    cout << backtracking(0,0,0,0);
}