728x90
반응형
1759 - 암호 만들기
https://www.acmicpc.net/problem/1759

문제
암호는 서로 다른 L개의 알파벳 소문자/ 최소 1개의 모음(a, e, i, o, u) + 최소 2개의 자음으로 구성
암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열
암호로 사용했을 법한 문자의 종류는 C가지
=> C개의 문자 모두 주어졌을 때, 가능성 있는 암호들 모두 구하기
입력
첫째 줄: 두 정수 L, C (3 <= L <= C <= 15)
다음 줄: C개의 문자 공백 구분 (중복 X)
출력: 각 줄에 하나씩, 사전식으로 가능성 있는 암호 모두 출력
풀이
DFS + Backtracking
모음 검사
static boolean isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
- `depth == L`: 모음 1개 이상 + 자음 2개 이상
- 지금 선택한 문자
- 모음 O -> `vowel` 카운트 + 1
- 자음 -> `consonant` 카운트 + 1
static void dfs(int start, int depth, int vowel, int consonant) {
if (depth == L) {
if (vowel >= 1 && consonant >= 2) {
sb.append(pwd).append('\n');
}
return;
}
for (int i = start; i < C; i++) {
char ch = arr[i];
pwd[depth] = ch;
if (isVowel(ch)) dfs(i + 1, depth + 1, vowel + 1, consonant);
else dfs(i + 1, depth + 1, vowel, consonant + 1);
}
}
코드
import java.io.*;
import java.util.*;
// 암호 만들기
public class boj_1759 {
static int L, C;
static char[] arr;
static char[] pwd;
static StringBuilder sb = new StringBuilder();
static boolean isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
static void dfs(int start, int depth, int vowel, int consonant) {
if (depth == L) {
if (vowel >= 1 && consonant >= 2) {
sb.append(pwd).append('\n');
}
return;
}
for (int i = start; i < C; i++) {
char ch = arr[i];
pwd[depth] = ch;
if (isVowel(ch)) dfs(i + 1, depth + 1, vowel + 1, consonant);
else dfs(i + 1, depth + 1, vowel, consonant + 1);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
L = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
pwd = new char[L];
arr = new char[C];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < C; i++) {
arr[i] = st.nextToken().charAt(0);
}
Arrays.sort(arr);
dfs(0, 0, 0, 0);
System.out.println(sb);
}
}728x90
반응형
'✏️ > BOJ' 카테고리의 다른 글
| [BOJ/DP] 백준 10942 - 팰린드롬? (Java) (0) | 2025.11.17 |
|---|---|
| [BOJ/Back-Tracking] 백준 1987 - 알파벳 (Java) (0) | 2025.11.17 |
| [BOJ/DP+Back-Tracking] 백준 9251 - LCS / 9252 - LCS 2 (Java) (0) | 2025.11.16 |
| [BOJ/DP] 백준 1149 - RGB 거리 / 17404 - RGB 거리 2 (Java) (0) | 2025.11.16 |
| [BOJ] 백준 2166 - 다각형의 면적 (Java) (0) | 2025.11.14 |