https://www.acmicpc.net/problem/1062
저는 조합을 통해 문제를 해결하였습니다.
' anta ', ' tica ' 이 둘은 무조건 포함되기에 'a','n','t','i','c'를 포함하고, 26-5개의 알파벳 중 k-5개를 뽑고, 그 알파벳으로 읽을 수 있는 문자열의 개수를 파악하고 이 값이 가장 큰 값을 찾아 문제를 해결하였습니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class BOJ_1062 {
private static final int ALPHA_SIZE = 26;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
boolean[][] usedAlpha = new boolean[n][ALPHA_SIZE];
for(int i = 0 ; i < n ; i++){
String str = br.readLine();
for(int j = 0 ; j < str.length() ; j++){
char ch = str.charAt(j);
usedAlpha[i][ch-'a'] = true;
}
}
if(m < 5){
System.out.println(0);
return ;
}
boolean[] choice = new boolean[ALPHA_SIZE];
choice['a' - 'a'] = true;
choice['n' - 'a'] = true;
choice['t' - 'a'] = true;
choice['i' - 'a'] = true;
choice['c' - 'a'] = true;
int result = cal(0,0,choice,usedAlpha,n,m-5);
System.out.println(result);
}
private static int cal(int depth, int start,boolean[] choice,boolean[][] usedAlpha, int n, int m) {
if(depth == m){
return findStr(choice,usedAlpha,n);
}
int result = 0;
for(int i = start ; i < ALPHA_SIZE ; i++){
if(choice[i]){
continue;
}
choice[i] = true;
result = Math.max(result,cal(depth+1,i+1,choice,usedAlpha,n,m));
choice[i] = false;
}
return result;
}
private static int findStr(boolean[] choice, boolean[][] usedAlpha, int n) {
int result = 0;
for(int i = 0 ; i < n ; i++){
boolean flag = true;
for(int j = 0 ; j < ALPHA_SIZE ; j++){
if(usedAlpha[i][j] && !choice[j]){
flag = false;
break;
}
}
if(flag){
result++;
}
}
return result;
}
}
'알고리즘' 카테고리의 다른 글
백준 15683번 감시 (JAVA) (0) | 2023.11.07 |
---|---|
백준 16234번 인구 이동 (JAVA) (3) | 2023.11.06 |
백준 14719번 빗물 (JAVA) (0) | 2023.11.04 |
백준 16236번 아기 상어 (JAVA) (0) | 2023.11.03 |
백준 1194번 달이 차오른다, 가자 (JAVA) (0) | 2023.11.02 |