1759 암호 만들기

2019. 8. 30. 10:22알고리즘/백준

백트래킹 문제

 

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

깃허브주소: https://github.com/surinoel/algorithm/blob/master/1759.cpp

 

깃허브 코드와는 다른 백트래킹 + 비트마스킹으로 해결

 

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
vector<char> vc;
void go(int idx, int maxcnt, int select) {
if (maxcnt == n) {
int ja, mo;
ja = mo = 0;
for (int i = 0; i < m; i++) {
if (select & (1 << i)) {
if (vc[i] == 'a' || vc[i] == 'e' || vc[i] == 'i' || vc[i] == 'o' || vc[i] == 'u') {
mo += 1;
}
else {
ja += 1;
}
}
}
if (ja >= 2 && mo >= 1) {
for (int i = 0; i < m; i++) {
if (select & (1 << i)) {
cout << vc[i];
}
}
cout << '\n';
}
return;
}
else if (idx == m) {
return;
}
go(idx + 1, maxcnt + 1, select | (1 << idx));
go(idx + 1, maxcnt, select);
}
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
vc.resize(m);
for (int i = 0; i < m; i++) {
cin >> vc[i];
}
sort(vc.begin(), vc.end());
go(0, 0, 0);
return 0;
}
view raw 1759.cpp hosted with ❤ by GitHub

'알고리즘 > 백준' 카테고리의 다른 글

11723 집합  (0) 2019.08.31
11660 구간 합 구하기 5  (0) 2019.08.31
14500 테트로미노  (0) 2019.08.29
16973 직사각형 탈출  (0) 2019.08.29
2548 대표 자연수  (0) 2019.08.29