# BOJ01062 가르침
https://www.acmicpc.net/problem/1062 (opens new window)
남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.
남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구한다.
# 문제의 이해
남극언어의 모든 단어는 anta와 tica로 끝나기 때문에 a, c, n, t, i는 읽일 수 있는 알파벳으로 판단한다. 5개의 알파벳을 제외하고 k개의 알파벳을 추가로 학습하여 읽을 수 있는 단어의 최대 개수를 구해야 한다.
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
k = scanner.nextInt();
words = new String[n];
for (int i = 0; i < n; i++) {
String word = scanner.next();
words[i] = word.replaceAll("anta|tica", ""); // (1)
}
if (k < 5) { // (2)
System.out.println("0");
return;
} else if (k == 26) { // (3)
System.out.println(n);
return;
}
// (4)
visited = new boolean[26];
visited['a' - 'a'] = true;
visited['c' - 'a'] = true;
visited['i' - 'a'] = true;
visited['n' - 'a'] = true;
visited['t' - 'a'] = true;
// (5)
backtracking(0, 0);
System.out.println(max);
}
(1) anta와 tica의 경우 이미 알고 있는 알파벳이기 때문에 제외하고 단어를 저장한다.
(2), (3) k < 5 인 경우 어떠한 단어도 읽을 수 없다. 최소 알고 있어야 하는 알파벳은 5개이기 때문이다. k == 26인 경우 모든 알파벳을 알기 때문에 읽을 수 없는 단어는 없다.
(4) 무조건 배울 수 있는 알파벳들을 true로 변경한다.
(5) 단어를 추가로 k - 5개를 배워가며 읽을 수 있는 단어를 판단한다.
# 백트래킹
private static void backtracking(int depth, int alphabet) {
if (depth == k - 5) { // (2)
int count = 0;
for (int i = 0; i < n; i++) {
boolean flag = true;
for (char c : words[i].toCharArray()) {
if (!visited[c - 'a']) {
flag = false;
break;
}
}
if (flag) {
count++;
}
}
max = Math.max(max, count);
return;
}
for (int i = alphabet; i < 26; i++) { // (1)
if (!visited[i]) {
visited[i] = true;
backtracking(depth + 1, i);
visited[i] = false;
}
}
}
(1) 배우지 않은 알파벳을 배우며 진행한다.
(2) 배울 수 있는 알파벳을 모두 배웠을 때 단어를 읽을 수 있는지 판단한다.
# 제출 코드
아래는 최종 제출 코드이다.
import java.util.Scanner;
public class BOJ1062 {
private static int n, k;
private static int max = Integer.MIN_VALUE;
private static boolean[] visited;
private static String[] words;
private static void backtracking(int depth, int alphabet) {
if (depth == k - 5) {
int count = 0;
for (int i = 0; i < n; i++) {
boolean flag = true;
for (char c : words[i].toCharArray()) {
if (!visited[c - 'a']) {
flag = false;
break;
}
}
if (flag) {
count++;
}
}
max = Math.max(max, count);
return;
}
for (int i = alphabet; i < 26; i++) {
if (!visited[i]) {
visited[i] = true;
backtracking(depth + 1, i);
visited[i] = false;
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
k = scanner.nextInt();
words = new String[n];
for (int i = 0; i < n; i++) {
String word = scanner.next();
words[i] = word.replaceAll("anta|tica", "");
}
if (k < 5) {
System.out.println("0");
return;
} else if (k == 26) {
System.out.println(n);
return;
}
visited = new boolean[26];
visited['a' - 'a'] = true;
visited['c' - 'a'] = true;
visited['i' - 'a'] = true;
visited['n' - 'a'] = true;
visited['t' - 'a'] = true;
backtracking(0, 0);
System.out.println(max);
}
}
# 비트마스킹
// TODO