1. 입력
- L, C (C개 중 L개 뽑기)
- 공백으로 문자 주어짐
2. 출력
- L개의 문자로 이루어진 암호 출력
3. 조건
- 모음 (a, e, i , o, u) 1개 이상
- 자음 2개 이상
4. 알고리즘
- 조합으로 풀면 된다.
C++)
- next_permutatoin
#include <iostream>
#include <algorithm> // sort, next_permutation
#include <vector>
#include <string>
using namespace std;
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int l, c;
cin >> l >> c;
vector<char> code;
vector<int> temp;
// 문자 입력받기
char ch;
for (int i = 0; i < c; i++) {
cin >> ch;
code.push_back(ch);
temp.push_back((i < l) ? 0 : 1); // 조합을 위해 확인
}
// 오름차순이어야하니까 정렬
sort(code.begin(), code.end());
int cnt1 = 0; // 모음
int cnt2 = 0; // 자음
do {
string str = "";
cnt1 = 0;
cnt2 = 0;
for (int i = 0; i < c; i++) {
if (temp[i] == 0) {
str += code[i];
if (code[i] == 'a' || code[i] == 'e' || code[i] == 'i' || code[i] == 'o' || code[i] == 'u')
cnt1++;
else
cnt2++;
}
}
// 모음 최소 1개 이상, 자음 최소 2개 이상 포함되어 있으면 암호로 사용할 수 있다
if (cnt1 >= 1 && cnt2 >= 2)
cout << str << "\n";
} while (next_permutation(temp.begin(), temp.end()));
return 0;
}
- dfs
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define MAX_NUM 17
using namespace std;
int l, c;
vector<string> ans;
char arr[MAX_NUM];
// 현재까지 만든 문자열, 시작 위치, 모음, 자음
void dfs(string str, int idx, int cnt1, int cnt2) {
if (str.length() == l) {
if (cnt1 >= 1 && cnt2 >= 2)
ans.push_back(str);
return;
}
for (int i = idx; i < c; i++) {
if (arr[i] == 'a' || arr[i] == 'e' || arr[i] == 'i' || arr[i] == 'o' || arr[i] == 'u')
dfs(str + arr[i], i + 1, cnt1 + 1, cnt2);
else
dfs(str + arr[i], i + 1, cnt1, cnt2 + 1);
}
}
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> l >> c;
for (int i = 0; i < c; i++)
cin >> arr[i];
sort(arr, arr + c);
dfs("", 0, 0, 0);
for (auto str : ans)
cout << str << "\n";
return 0;
}
Python)
- 백트래킹
import sys
read = sys.stdin.readline
l, c = map(int, read().rstrip().split())
arr = list(read().rstrip().split())
arr = sorted(arr)
ans = [0]*l
def is_password():
cnt_1 = 0 # 모음
cnt_2 = 0 # 자음
for ch in ans:
if ch in ['a', 'e', 'i', 'o', 'u']:
cnt_1 += 1
else :
cnt_2 += 1
if cnt_1 >= 1 and cnt_2 >= 2:
return True
else :
return False
def func(cnt, idx):
if cnt == l:
if is_password():
print(''.join(ans))
return
for i in range(idx, c):
ans[cnt] = arr[i]
func(cnt+1, i+1)
func(0, 0)
'백준 2 > 백트래킹' 카테고리의 다른 글
| [백준 15663] N과 M (9) (C++/Python) (0) | 2023.07.28 |
|---|---|
| [백준 15686] 치킨배달 (C++/Python) (0) | 2020.12.07 |
| [백준 6603] 로또 (C++/Python) (0) | 2020.12.07 |
| [백준 1987] 알파벳 (0) | 2020.12.07 |
| [백준 9663] N-Queen (0) | 2020.12.07 |