https://school.programmers.co.kr/learn/courses/30/lessons/84512
경우의 수 규칙이 있을거같았는데 생각하기 복잡해서 문제의 카테고리인 완전탐색으로 풀었다.
dfs 재귀를 만들어서 풀었다.
일단 정답을 찾은경우 재귀를 빨리 끝내기 위해 count == answer일 경우 return을 해두었다.
재귀 안에 for문으로 글자를 더한 후 카운트 증가 후 word가 검출되면 answer를 count로 갱신하고 return 한다.
start의 길이가 5일때 까지 재귀한다. 돌아오면 넣었던 마지막 글자를 뺴고 for문으로 인해 다음 글자를 넣고 다시 재귀한다.
#include <string>
#include <vector>
using namespace std;
string AEIOU = "AEIOU";
int count = 0;
int answer = -1;
void dfs(string start, string word)
{
if(count == answer)
return;
for(int i = 0; i < 5; i++)
{
start += AEIOU[i];
count++;
if(start == word)
{
answer = count;
return;
}
if(start.length() < 5)
dfs(start, word);
start.pop_back();
}
}
int solution(string word) {
dfs("", word);
return answer;
}
#include <string>
#include <vector>
#include <map>
using namespace std;
int solution(string word) {
int answer = 0;
map<char, int> alp;
int next_word[5] = { 781, 156, 31, 6, 1 };
alp.insert({'A', 0});
alp.insert({'E', 1});
alp.insert({'I', 2});
alp.insert({'O', 3});
alp.insert({'U', 4});
int i = 0;
for (const auto& w : word) {
answer += 1 + alp[w] * next_word[i];
i++;
}
return answer;
}
https://ggjjdiary.tistory.com/68
대부분은 완전탐색으로 했고 규칙을 찾은 답안을 가져왔다.