링크 : https://www.acmicpc.net/problem/1759
1759번: 암호 만들기
첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.
www.acmicpc.net
TIL
1) 풀면서 놓쳤던 점
놓쳤던 점이라기보단, >모음은 최소 한개, 자음은 최소 두개< 라는 조건을 어떤식으로 구현할지에 대해 ..
나는 dfs 탈출조건에서 마지막에 확인하게 한거라 약간 비효율적이지 않나 싶었다.
모음은 다섯개고, 자음은 모음 이외니까 쉽게 처리할수있었지만, 만약 더 갯수가 여러개거나 복잡해진다면, 결코 내 방법은 효율적이라고 보기 어려울듯하다.
마지막 dfs까지 갈 필요 없이, 그 전에 조건을 확인할 수 있는 방법에 대해 고민수 .. 벗 맞았으니까 ㅎㅎ 기분은 굳
그래두 좀더 고민해볼라구 여기다 적어둔다 ㅎㅎ
정답 코드
#include<cstdio>
#include<algorithm>
int L, C; // L : 사용한 알파벳 종류 수, C : 가능한 알파벳 종류 수
char before = 0; // 오름차순 출력을 위한 변수
char alpha[15 + 1];
bool visit[15 + 1]; // dfs용
char printa[15 + 1]; // 출력할 알파벳 배열
int mocnt, jacnt;
void dfs(int cnt) {
if (cnt == L) {
mocnt = jacnt = 0;
for (int j = 0; j < L; j++) {
if (printa[j] == 'a' || printa[j] == 'e' || printa[j] == 'i' || printa[j] == 'o' || printa[j] == 'u') {
mocnt++;
}
else jacnt++;
}
if (mocnt < 1 || jacnt < 2) return;
else {
for (int j = 0; j < L; j++) {
printf("%c", printa[j]);
}
puts("");
return;
}
}
for (int i = 0; i < C; i++) {
if (!visit[i] && alpha[i]>before) { // before : 오름차순을 위한 이전 알파벳과 비교
visit[i] = true;
printa[cnt] = alpha[i];
dfs(cnt + 1);
before = alpha[i];
visit[i] = false;
}
}
}
int main() {
scanf("%d %d", &L, &C);
for (int i = 0; i < C; i++)
scanf(" %c", &alpha[i]);
std::sort(alpha, alpha + C);
dfs(0);
return 0;
}