백준 1759번 - 암호 만들기
문제 풀이
먼저 입력 값들을 알파벳 순서대로 정렬을 해주고 백트래킹을 통해서 완전 탐색을 실시한다.
적당히 값들을 다 뽑아주었으면 알파벳 순서대로 정렬되어있는지 체크를 하고, 모음이 1개 이상이고 자음이 2개 이상인지 체크를하고 모두 통과되면 출력해주는 방식으로 풀었다.
문제 링크
소스코드
#include <iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<queue>
#include<memory.h>
using namespace std;
int l, c;
char arr[17];
vector<char> selected;
bool visit[17];
void solution(int idx , int cnt, int max);
int main() {
cin >> l >> c;
for (int i = 0; i < c; i++)
{
cin >> arr[i];
}
sort(arr, arr + c);
solution(0,0, l);
}
void solution(int idx , int cnt, int max)
{
if (cnt == max)
{
//순서 체크
for (int i = 0; i < max - 1; i++)
{
if (selected[i] > selected[i + 1])
return;
}
int chk1=0, chk2=0;
for (int i = 0; i < max; i++)
{
if (selected[i] == 'a' || selected[i] == 'e' || selected[i] == 'i' || selected[i] == 'o' || selected[i] == 'u')
chk1++;
else
chk2++;
}
if (chk1 <= 0 || chk2 < 2)
return;
for (int i = 0; i < max; i++)
{
cout << selected[i];
}
cout << '\n';
return;
}
for (int i = idx; i < c; i++)
{
if (visit[i] == 0)
{
visit[i] = 1;
selected.push_back(arr[i]);
solution(i+ 1, cnt + 1, max);
visit[i] = 0;
selected.pop_back();
}
}
}
Author And Source
이 문제에 관하여(백준 1759번 - 암호 만들기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@pjh612/백준-1759번-암호-만들기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)