1759 암호 만들기
2019. 8. 30. 10:22ㆍ알고리즘/백준
백트래킹 문제
문제: https://www.acmicpc.net/problem/1759
깃허브주소: https://github.com/surinoel/algorithm/blob/master/1759.cpp
깃허브 코드와는 다른 백트래킹 + 비트마스킹으로 해결
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
'알고리즘 > 백준' 카테고리의 다른 글
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 |