백준 1759번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
2초	128MB	골드 5

---

풀이

 문제를 읽어보면 정말 익숙한 그 냄새가 난다. N과 M 문제의 냄새가 말이다. 따라서 이 문제는 백트래킹이다. 물론 문자의 개수가 많지 않고 시간제한이 2초나 되기 때문에 입력받은 문자를 자음과 모음으로 나누어 일일이 브루트포스를 해도 답은 맞을 것 같다.

 

 처음 문제를 풀고나선 WA를 받았는데, 자음 조건을 놓쳐서 틀렸다. 이런 실수는 줄여나가야 하는데 말이다...

코드

#include <bits/stdc++.h>
#define ALL(X) X.begin(), X.end()
#define endl '\n'
using namespace std;

int l, c;
string pwd, vowels, consonants;

void input() {
	string all_vowels = "aeiou";
	char a;
	cin >> l >> c;

	while(pwd.length() < c) {
		cin >> a;
		if (a != ' ') pwd += a;
		if (all_vowels.find(a) != string::npos) {
			vowels += a;
		}
		else {
			consonants += a;
		}
	}

	sort(ALL(pwd));
	sort(ALL(vowels));
}

void sol(int idx, string output) {
	if (output.length() == l) {
		int vo_count = 0, con_count = 0;

		for(char& v : vowels) {
			if (output.find(v) != string::npos) {
				vo_count++;
				break;
			}
		}

		for(char& c : consonants) {
			if (con_count == 2) {
				break;
			}
			if (output.find(c) != string::npos) {
				con_count++;
			}
		}

		if (vo_count == 1 && con_count == 2) {
			cout << output << endl;
		}

		return;
	}
	else if (idx >= c) {
		return;
	}

	for(; idx < c; idx++) {
		sol(idx + 1, output + pwd[idx]);
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	input();
	sol(0, "");
}