[BOJ]1759번: 암호 만들기 (c++)

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

1759번: 암호 만들기

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// 최소 모음 1개, 자음 2개 조건에 만족하는지 검사
bool check(string pw)
{
	const string consonant = "aeiou";

	int c_cnt = 0;
	for (char c : pw)
	{
		if (consonant.find(c) != string::npos)
		{
			++c_cnt;
		}
	}

	return (c_cnt >= 1 && pw.length() - c_cnt >= 2);
}

void dfs(vector<char> &chars, string pw, int L, int index)
{
	// L자리가 완성되면 출력
	if (pw.length() == L)
	{
		if (check(pw))
		{
			cout << pw << '\n';
		}
		return;
	}
	// L자리가 완성되기 전에 index가 범위를 넘어버린 경우
	else if (index == chars.size())
	{
		return;
	}

	// chars[index]를 선택하는 경우
	dfs(chars, pw + chars[index], L, index + 1);

	// chars[index]를 선택하지 않는 경우
	dfs(chars, pw, L, index + 1);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 입력
	int L, C;
	cin >> L >> C;
	vector<char> chars(C);
	for (int i = 0; i < C; ++i)
	{
		cin >> chars[i];
	}
	// 오름차순 정렬
	sort(chars.begin(), chars.end());

	// dfs - 백트랙킹으로 문자 조합
	dfs(chars, "", L, 0);

	return 0;
}

 

 

풀고나니 로또 문제와 매우 비슷하다.

 

 

TIP

모든 케이스를 다 만들고 난 뒤에, 문제 조건을 만족하는지 검사하면 된다.

암호는 서로 다른 L개의 알파벳 소문자들로 구성되며
암호로 사용했을 법한 문자의 종류는 C가지
(3 ≤ L ≤ C ≤ 15)

 

여기서 최대의 경우 2^15 가지를 검사하게 되는데,

2^10 = 1024 이므로, 2^20 라고 해도 대략 100만쯤 될것이다. 

따라서 2^15가지를 만드는 게 그리 큰 시간적 비용이 아닌 것을 확인할 수 있다.