728x90
반응형
문제 출처 : https://www.acmicpc.net/problem/1759
1759번: 암호 만들기
첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.
www.acmicpc.net
풀이
dfs를 사용하여 해결한 문제이다.
dfs에서 알파벳을 하나씩 추가한뒤, L개가 되면 모음 조건 && 자음 조건을 확인해 처리하였다.
str.push_back(v[now]);
if(v[now] == 'a' || v[now] == 'e' || v[now] == 'i' || v[now] == 'o' || v[now] == 'u')
vowel++;
else conso++;
if(str.length() == L){
if(vowel >= 1 && conso >= 2)
cout << str << '\n';
return;
}
여기서 배운점은, 자음의 수는 그냥 L - 모음의 수로 처리할 수 있었다...!
코드
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int L, C;
// conso : 자음 개수, vowel : 모음 개수
void dfs(vector<char> v, int now, string str, int conso, int vowel){
str.push_back(v[now]);
if(v[now] == 'a' || v[now] == 'e' || v[now] == 'i' || v[now] == 'o' || v[now] == 'u')
vowel++;
else conso++;
if(str.length() == L){
if(vowel >= 1 && conso >= 2)
cout << str << '\n';
return;
}
for(int i = now + 1; i < C; i++)
dfs(v, i, str, conso, vowel);
return;
}
int main(){
ios::sync_with_stdio(false); cin.tie(NULL);
cin >> L >> C;
vector<char> v(C);
for(int i = 0; i < C; i++)
cin >> v[i];
sort(v.begin(), v.end());
for(int i = 0; i <= C - L; i++)
dfs(v, i, "", 0, 0);
return 0;
}
728x90
반응형
'Tech > Algorithm' 카테고리의 다른 글
[BOJ] 백준 1987 알파벳 c++ (dfs, 백트래킹, 그래프) (0) | 2022.01.17 |
---|---|
[BOJ] 백준 1182 부분수열의 합 c++ (dfs, 백트래킹, 브루트포스) (0) | 2022.01.17 |
[BOJ] 백준 6603 로또 c++ (dfs, next_permutation) (0) | 2022.01.13 |
[BOJ] 백준 1065 한수 c++ (브루트포스) (0) | 2022.01.11 |
[프로그래머스] 소수 찾기 c++ (완전탐색, 에라토스테네스의 체) (0) | 2022.01.09 |