반응형
리뷰
최소 한 개의 모음과 최소 두 개의 자음으로 구성된 정렬된 문자열의 암호를 찾는 문제
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)
- 백트래킹을 통해 암호가 될 수 있는 문자열의 조합을 찾아내는 함수
- 매개변수로 재귀 단계 level, 현재의 문자열 cur, 자음의 개수 ja, 모음의 개수 mo를 전달받는다.
- c개의 문자열을 탐색해 준다, 만약 방문 처리가 되있거나, 이전의 문자보다 지금의 문자가 작으면 continue
- 조건에 걸리지 않았다면 현재 알파벳을 방문처리 해준다.
- 정수형 두개를 pair로 갖는 chk변수를 값을 0으로 초기화 해준다.
- 만약 현재 문자가 모음이라면 chk를 {1, 0}으로 아니라면 {0, 1}로 만들어 준다.
- 재귀 단계를 높히고 cur에 현재 문자를 더해주고 ja엔 chk의 second를 mo엔 chk의 first를 더해준 뒤 재귀를 실행한다.
- 재귀가 종료된 후엔 방문처리만 해제해 주면 된다.
- 기저조건은 재귀 단계 level이 l에 도달했을 때이다.
- 만약 자음이 2개 이상 모음이 1개 이상이라면 cur에 저장된 문자열을 출력해 준 뒤 리턴해 준다.
문제풀이
- l,c를 입력 받고 lst에 c개의 문자를 입력 받아준다. 이후 lst배열을 오름차순으로 정렬해 준다.
- 백트래킹을 시작한다, 기저조건, 자음의 수, 모음의 수는 모두 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
반응형
'알고리즘 공부 > C++' 카테고리의 다른 글
[S1] 백준 11403번 경로 찾기 C++ 플로이드 와샬, 최단 경로 (0) | 2024.10.04 |
---|---|
[G4] 백준 11404번 플로이드 C++ 플로이드 와샬, 최단 경로 (0) | 2024.10.04 |
[G3] 백준 16954번 움직이는 미로 탈출 C++ 백트래킹 (0) | 2024.10.02 |
[G3] 백준 2812번 크게 만들기 C++ 스택, 문자열, 그리디 알고리즘 (0) | 2024.10.02 |
[G5] 백준 6198번 옥상 정원 꾸미기 C++ 스택 (0) | 2024.10.02 |