https://www.acmicpc.net/problem/1759
문제
> 바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다.
> 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다.
> 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다.
> 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다.
> 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.
> 새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다.
> 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다.
> C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.접근
주어진 문자를 입력받으면서 이 중 모음을 따로 모아둔다.
입력을 다 받으면 문자를 사전순으로 정렬해두고 백트래킹으로 가능한 모든 조합을 L길이 만큼 만드는 Password 메소드를 통해 암호를 만든다.
일단 가능한 모든 경우를 만들면서 길이가 L에 도달하면 검사를 한다.
만들어진암호에 포함된 문자를 사전에 미리 모아놨던 모음과 비교해 하나라도 같다면 모음개수를 누적하고, 전부 다르면 자음개수를 누적해나간다.
모든 비교가 끝나면 모음의 개수가 1개 이상이며 자음개수가 2개 이상인지 검사하고 맞다면 출력, 아니면 넘어간다.
문제해결
> L과 C를 입력받고, 문자를 저장할 벡터 word를 선언해 C개만큼 받는다.
> 문자를 입력받으며 모음인지 검사해 모음이라면 따로 tmp 벡터에 모음 종류를 저장해둔다.
> sort로 사전순 정렬해주고 Password메소드에 모든 경우를 따지기 위해 인덱스 번호 0번과 길이 0을 넣고 호출한다.
> 메소드안에선 기본적으로 들어온 idx부터 시작해서 모든 문자 C개를 반복문으로 돈다. 가능한 암호인 result벡터에 저장해가며 재귀로 i+1번 문자부터 시작하도록 호출해준다.
> 재귀를 하다 rst가 L값과같으면 암호의 길이를 만족하므로 검증한다.
> 만들어진 암호 result를 한 자리씩 돌며 tmp에 있는 입력받았던 모음과 비교한다. 같아면 valid가 true로 아래에서 cnt1(모음 수 누적변수)을 증가시키고, false면 모음이 아니라는 뜻이므로 cnt2를 증가시킨다.
> 반복문이 끝나고 cnt1과 cnt2에 누적된 수를 문제의 조건대로 모음1이상, 자음2이상으로 검증해 맞다면 출력, 아니면 넘긴다.코드
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
int L, C;
vector<char> word;
vector<char> result;
vector<char> tmp;
void Password(int idx, int rst)
{
if (rst == L)
{
int cnt1 = 0; // 모음
int cnt2 = 0; // 자음
string str = "";
for (int i = 0; i < result.size(); i++)
{
bool valid = false;
for (int j = 0; j < tmp.size(); j++)
{
if (result[i] == tmp[j])
{
valid = true;
break;
}
}
str += result[i];
if (valid) cnt1++;
else cnt2++;
}
if (cnt1 >= 1 && cnt2 >= 2)
cout << str << '\n';
}
for (int i = idx; i < C; i++)
{
result.push_back(word[i]);
Password(i+1, rst + 1);
result.pop_back();
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> L >> C;
word.resize(C);
for (int i = 0; i < C; i++)
{
char c;
cin >> c;
word[i] = c;
if (c == 'a' || c == 'o' || c == 'e' || c == 'i' || c == 'u')
{
tmp.push_back(c);
}
}
sort(word.begin(), word.end());
Password(0, 0);
}
후기
문제의 조건을 잘못봐 모음의 개수만 따져서 틀렸다.
