Algorithm/dfs
백준 1759 암호만들기 c++ // 포함불포함 완탐 dfs, 순열시간초과 나는경우 해결
Mini_96
2023. 11. 26. 17:03
https://www.acmicpc.net/problem/1759
1759번: 암호 만들기
첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.
www.acmicpc.net
1. 순열시간초과 나는경우 해결
15! == 시간초과
해결 -> 포함,불포함 완탐 (2^15 == 32768)
2. 전체코드
#include <bits/stdc++.h>
using namespace std;
int l, c, visited[16];
vector<char> v;
int mo[128];
//현재까지 k번인덱스까지 포함,미포함 판단함 / 모음갯수/ tempStr
void dfs(int k, int cnt, string s) {
if (k == c) { //리프노드까지 모두탐색함
if (s.size() == l && cnt >= 1 && l - cnt >= 2) {
cout << s << "\n";
}
return;
}
//k번째 문자를 포함하는경우
dfs(k + 1, cnt+mo[v[k]], s + v[k]);
//포함안하는경우
dfs(k+1, cnt, s);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> l >> c;
mo['a'] = 1, mo['e'] = 1, mo['i'] = 1, mo['o'] = 1,mo['u']=1;
for (int i = 0; i < c; ++i) {
char c;
cin >> c;
v.push_back(c);
//a.push_back(i);
}
sort(v.begin(), v.end());
dfs(0, 0, "");
return 0;
}