알고리즘 공부/C++

[G5] 백준 1759번 암호 만들기 C++ 백트래킹

마달랭 2024. 10. 3. 19:19
반응형

리뷰

 

최소 한 개의 모음과 최소 두 개의 자음으로 구성된 정렬된 문자열의 암호를 찾는 문제

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

 

전역 변수

  • l, c : 암호의 길이 l, 암호로 사용했을 법한 문자의 종류 c
  • lst : 암호로 사용했을 법한 문자를 저장할 문자 배열, 크기는 16으로 초기화 한다.
  • v : 방문 처리를 체크할 용도의 정수형 배열, 크기는 16으로 초기화 한다.

 

함수

1. bt

void bt(int level, string cur, int ja, int mo)

 

  1. 백트래킹을 통해 암호가 될 수 있는 문자열의 조합을 찾아내는 함수
  2. 매개변수로 재귀 단계 level, 현재의 문자열 cur, 자음의 개수 ja, 모음의 개수 mo를 전달받는다.
  3. c개의 문자열을 탐색해 준다, 만약 방문 처리가 되있거나, 이전의 문자보다 지금의 문자가 작으면 continue
  4. 조건에 걸리지 않았다면 현재 알파벳을 방문처리 해준다.
  5. 정수형 두개를 pair로 갖는 chk변수를 값을 0으로 초기화 해준다.
  6. 만약 현재 문자가 모음이라면 chk를 {1, 0}으로 아니라면 {0, 1}로 만들어 준다.
  7. 재귀 단계를 높히고 cur에 현재 문자를 더해주고 ja엔 chk의 second를 mo엔 chk의 first를 더해준 뒤 재귀를 실행한다.
  8. 재귀가 종료된 후엔 방문처리만 해제해 주면 된다.
  9. 기저조건은 재귀 단계 level이 l에 도달했을 때이다.
  10. 만약 자음이 2개 이상 모음이 1개 이상이라면 cur에 저장된 문자열을 출력해 준 뒤 리턴해 준다.

 

문제풀이

  1. l,c를 입력 받고 lst에 c개의 문자를 입력 받아준다. 이후 lst배열을 오름차순으로 정렬해 준다.
  2. 백트래킹을 시작한다, 기저조건, 자음의 수, 모음의 수는 모두 0이며 문자열은 빈 문자열을 전달한다.

 

참고 사항

또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다.

즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.

이 말의 뜻은 입력받은 문자들을 한번 정렬하고 시작하면 더 수월하다는 뜻이다.

 

정답 코드

#include<iostream>
#include<algorithm>

using namespace std;
int l, c;
char lst[16];
int v[16];

void bt(int level, string cur, int ja, int mo) {
	if (level == l) {
		if (ja >= 2 && mo >= 1) cout << cur << "\n";
		return;
	}
	for (int i = 0; i < c; i++) {
		if (v[i]) continue;
		if (!cur.empty() && cur.back() > lst[i]) continue;
		v[i] = 1;
		pair<int, int> chk = { 0, 0 };
		if (lst[i] == 'a' || lst[i] == 'e' || lst[i] == 'i' || lst[i] == 'o' || lst[i] == 'u') chk.first++;
		else chk.second++;
		bt(level + 1, cur + lst[i], ja + chk.second, mo + chk.first);
		v[i] = 0;
	}
}

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

	cin >> l >> c;
	for (int i = 0; i < c; i++) cin >> lst[i];
	sort(lst, lst + c);
	bt(0, "", 0, 0);
}

 

 

728x90
반응형