백준 1759번: 암호 만들기 - DFS, 백트래킹, 조합 응용 C++

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

 

1759번: 암호 만들기

1. 문제설명

순열이나 조합을 만드는 문제와 비슷하다. 차이점은 숫자 대신 문자를 출력한다는 점이다.

조건에서 구해야 하는 암호는 항상 사전순으로 이루어져있어야하고

최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있어야한다.

 

 

입력

4 6
a t c i s w

출력

acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

 

 

2. 접근 방법[알고리즘]

먼저 증가하는 순열(조합)을 만들고 그 순열에 알파벳 순으로 덮어준다고 생각하면 쉽다.

다만 문제에서 사전순이라는 조건과 모음과 자음의 갯수 조건이 있으므로

우선 알파벳 순열을 만들어주고 그 알파벳 순열이 조건에 부합한다면 출력해주면 된다.

 

 

 

우선 증가하는 순열을 만들어보자. 

6개의 숫자에서 4개의 숫자를 뽑는 조합을 만든다고 생각해도 동일하다.

#include <bits/stdc++.h>
using namespace std;

int L, C, path[20], ch[20] , t=1;
char a[20], ans[20];

void DFS(int cur) {
	if (t == L+1) {
		for (int i = 1; i <= L; i++) {
			cout << path[i] << ' ';
		}
		cout << '\n';

	}
	else {
		for (int i = cur; i <= C; i++) {
			if (ch[i] == 0) {
				ch[i] = 1;
				path[t++] = i;
				DFS(i);
				ch[i] = 0;
				t--;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> L >> C;


	DFS(1);
}

 

조합 출력

 

이제 각 숫자에 해당 알파벳을 적용하면 된다

알파벳은 문제 조건에 따라 사전순으로 정렬되어야한다.

a t c i s w

번호	1	2	3	4	5	6
알파벳	a	c	i	s	t	w

 

1759 암호만들기

이제 알파벳 까지 적용해서 잘 만들었다.

하지만 cstw는 문제 조건에서 모음이 한개이상 있어야하므로 출력되면 안된다.

↓ 지금 단계 까지의 코드

#include <bits/stdc++.h>
using namespace std;

int L, C, path[20], ch[20] , t=1;
char a[20], ans[20];

void DFS(int cur) {
	if (t == L+1) {
		int cnt1 = 0;
		//for (int i = 1; i <= L; i++) {
		//	ans[i] = a[path[i]];
		//	if (ans[i] == 'a' || ans[i] == 'e' ||
		//		ans[i] == 'i' || ans[i] == 'o' || ans[i] == 'u') {
		//		cnt1++;
		//	}
		//}

		//if (cnt1 >= 1 && L - cnt1 >= 2) {
		//	for (int i = 1; i <= L; i++) {
		//		cout << ans[i];
		//	}
		//	cout << '\n';

		//}

		for (int i = 1; i <= L; i++) {
			cout << a[path[i]] << ' ';
		}
		cout << '\n';

	}
	else {
		for (int i = cur; i <= C; i++) {
			if (ch[i] == 0) {
				ch[i] = 1;
				path[t++] = i;
				DFS(i);
				ch[i] = 0;
				t--;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> L >> C;

	for (int i = 1; i <=C; i++) {
		cin >> a[i];
	}
	sort(a+1 , a + 1 + C);

	DFS(1);
}

 

마지막으로 출력하기전에 모음과 자음 갯수를 카운트해

조건에 부합하면 출력하면된다.

cnt1 변수로 모음갯수만 세서 전체 알파벳 갯수인 L에서 cnt1을 빼주면 자음갯수를 구할 수 있다.

 

3.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int L, C, path[20], ch[20] , t=1;
char a[20], ans[20];

void DFS(int cur) {
	if (t == L+1) {
		int cnt1 = 0;
		for (int i = 1; i <= L; i++) {
			ans[i] = a[path[i]];
			if (ans[i] == 'a' || ans[i] == 'e' ||
				ans[i] == 'i' || ans[i] == 'o' || ans[i] == 'u') {
				cnt1++;
			}
		}

		if (cnt1 >= 1 && L - cnt1 >= 2) {
			for (int i = 1; i <= L; i++) {
				cout << ans[i];
			}
			cout << '\n';

		}
	}
	else {
		for (int i = cur; i <= C; i++) {
			if (ch[i] == 0) {
				ch[i] = 1;
				path[t++] = i;
				DFS(i);
				ch[i] = 0;
				t--;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> L >> C;

	for (int i = 1; i <=C; i++) {
		cin >> a[i];
	}
	sort(a+1 , a + 1 + C);

	DFS(1);
}

DFS, 백트래킹을 이용하여 조합을 만들어주고

 

문제 조건을 적용하면 해결되는 문제이다.