이번에 풀어본 문제는
백준 1062번 가르침 입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
static int N,K;
static boolean [] isLearned;
static List<String> dic;
static int answer;
static int learnCount;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
isLearned = new boolean[26];
// a, c, i, n, t는 기본으로 배워야함
isLearned[0] = true;
isLearned[2] = true;
isLearned[8] = true;
isLearned[13] = true;
isLearned[19] = true;
learnCount = K - 5;
if (learnCount >= 0) {
dic = new ArrayList<>();
for (int i = 0; i < N; i++) {
String input = br.readLine();
// anta, tica 자름
String str = input.substring(4, input.length() - 4);
dic.add(str);
}
dfs(0,0);
}
System.out.print(answer);
}
static void dfs(int start, int count) {
if (count == learnCount) {
answer = Math.max(answer, readDic());
return;
}
for (int i = start; i < 26; i++) {
if (!isLearned[i]) {
isLearned[i] = true;
dfs(i, count + 1);
isLearned[i] = false;
}
}
}
static int readDic() {
int tmp = 0;
next : for (String str : dic) {
int strLen = str.length();
for (int i = 0; i < strLen; i++) {
if (!isLearned[str.charAt(i) - 97]) continue next;
}
tmp++;
}
return tmp;
}
}
학생들에게 K개의 문자를 가르쳐, N개의 문자열 중 가장 많이 읽을 수 있는 경우를 구하는 문제입니다.
주어지는 문자열은 anta로 시작하고 tica로 끝난다는 규칙이 존재하기 때문에, 최소 a,c,i,n,t 5가지 문자는 무조건 가르쳐야 합니다.
따라서 K값이 5보다 작은 경우는 0을 출력해줍니다.
이외 경우에서는 가르칠 수 있는 모든 경우의 수를 고려하여 문자열을 읽을 수 있는 최댓값을 누적하여 최종 출력해주면 해결할 수 있습니다.
문제가 꽤나 복잡하게 설명되어 있는 것 같습니다ㅠ