알고리즘 문제 풀이/백준
[백준] 암호 만들기 - 1759번
h982
2021. 7. 6. 21:46
문제설명
https://www.acmicpc.net/problem/1759
1759번: 암호 만들기
첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.
www.acmicpc.net
기본아이디어
최소 한개의 모음과 최소 두개의 자음으로 구성된 길이 L인 문자열을 만들면 된다.사전순으로 출력을 해야하기 때문에 가능한 경우를 dfs 탐색으로 찾으면 된다. 선택된 문자들이 길이가 L이 되면 그때모음이 한개 이상이고 자음이 두개 이상인지 검사를 하고 통과하면 정답으로 출력을 해준다.
구현코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
public static void main(String[] args) throws IOException {
StringTokenizer st = new StringTokenizer(input.readLine());
L = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
words = new char[C];
st = new StringTokenizer(input.readLine());
for(int i = 0;i < C; i++){
words[i] = st.nextToken().charAt(0);
}
selected = new char[L];
Arrays.sort(words);
comb(0, 0);
System.out.println(output);
}
static int L, C;
static char[] words;
static char[] mo = {'a', 'e', 'i', 'o', 'u'};
static char[] selected;
static void comb(int idx, int cnt){
if(cnt == L){
if (isOk()) {
for (int i = 0; i < L; i++) {
output.append(selected[i]);
}
output.append("\n");
}
return;
}
for(int i = idx; i < C; i++){
selected[cnt] = words[i];
comb(i+1, cnt+1);
}
}
static boolean isOk(){
int mo_cnt = 0;
for(int i = 0; i < L; i++){
char temp = selected[i];
for(int j = 0; j < mo.length; j++){
if(temp == mo[j]){
mo_cnt++;
break;
}
}
}
if(mo_cnt >= 1 && L-mo_cnt >= 2)
return true;
return false;
}
|
cs |
정리, 기억할 내용
1. 문제를 잘 읽자.