import java.io.*; import java.util.*; public class Main { static boolean[] alpha; static int N, K; static int answer; static ArrayList words; static HashSet hs; //단어들에 있는 antic를 제외한 글자를 모은 set public static boolean checkWord(String s) { char[] c = s.toCharArray(); for(int i = 0; i < s.length(); i++) { if(!alpha[c[i]-'a']) { return false; } } return true; } public static void select(int cnt, int index) { if(cnt == K) { int ret = 0; for(String s : words) { if(checkWord(s)) { ret++; } } answer = Math.max(answer, ret); return; } for(int i = index; i < 26; i++) { if(!alpha[i]) { alpha[i] = true; select(cnt+1, i+1); alpha[i] = false; } } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); alpha = new boolean[26]; alpha[0] = true; //a alpha[2] = true; //c alpha[8] = true; //i alpha[13] = true; //n alpha[19] = true; //t N = Integer.parseInt(st.nextToken()); K = Integer.parseInt(st.nextToken()); hs = new HashSet<>(); words = new ArrayList<>(); if(K < 5) { System.out.println(0); } else if(K == 26) { System.out.println(N); } HashSet set; int temp = N; for(int i = 0; i < N; i++) { String s = br.readLine(); if(s.length() == 8) { //antatica인 경우 answer++; continue; } set = new HashSet<>(); char[] c = s.toCharArray(); for(char ch : c) { set.add(ch-'a'); } int cnt = set.size(); if(cnt > K) { temp--; continue; //필요 글자가 K보다 많은 경우 } if(cnt == 5) { //a, n, t, i, c만 있는 경우 answer++; continue; } for(char ch : c) { //필요한 글자 모으기 if(!alpha[ch-'a']) { hs.add(ch-'a'); } } words.add(s.substring(4, s.length()-4)); } answer = 0; if(K >= 5) { if(hs.size() <= K-5) { System.out.println(temp); } else { select(5, 0); System.out.println(answer); } } } }

제출 #20596

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: