ALGORITHM/BOJ
[백준] 1062 가르침
0298
2021. 2. 15. 21:18
1062번: 가르침
첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문
www.acmicpc.net
2021-02-15
|
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
public static int N, K, answer;
public static String arr[];
public static char alpha[] = {'b', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'l', 'm', 'o', 'p', 'q'
,'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
public static boolean vtd[];
public static int check() {
int ans = 0;
for(int i = 0; i < N; i++) {
int cnt = 0;
for(int j = 0; j < arr[i].length(); j++) {
int idx = arr[i].charAt(j) - 'a';
if(vtd[idx]) cnt++;
}
if(cnt == arr[i].length()) ans++;
}
return ans;
}
public static void solve(int idx, int cnt) {
if(cnt == K-5) {
answer = Math.max(answer, check());
return;
}
for(int i = idx; i < alpha.length; i++) {
int k = alpha[i] - 'a';
if(!vtd[k]) {
vtd[k] = true;
solve(i, cnt+1);
vtd[k] = false;
}
}
}
public static void main(String[] args) throws Exception{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
arr = new String[N];
vtd = new boolean[27];
answer = 0;
for(int i = 0; i < N; i++) {
st = new StringTokenizer(bf.readLine().trim());
String str = st.nextToken();
arr[i] = str.substring(4, str.length()-4);
}
if(K >= 5) {
vtd['a'-'a'] = true;
vtd['c'-'a'] = true;
vtd['n'-'a'] = true;
vtd['i'-'a'] = true;
vtd['t'-'a'] = true;
solve(0, 0);
} else answer = 0;
System.out.println(answer);
}
}
|
cs |
#문체풀이