[프로그래머스] 모음사전 c++

 

풀이
백트래킹을 이용해 풀었다. 사용했던 원소를 계속 사용할 수 있기 때문에 chk배열을사용하지 않고 풀었다. 

#include <string>
#include <vector>

using namespace std;
string end_s;
int chk[5];
string alphabet = "AEIOU";
int answer ;
int cnt;

void dfs(string s){

	//원하는 단어가 있다면 리턴한다.
    if(s==end_s)
    {
        answer=cnt;
        return;
    }
    //길이가 5이하인 단어를 만든다.
    if(s.size()>4)
        return;
    for(int i=0;i<5;i++){
        cnt++;
        dfs(s+alphabet[i]);
    }
}
int solution(string word) {
    end_s=word;
    dfs("");
    return answer;
}