import java.io.*; import java.util.*; public class Main { static boolean[] alpha; static int N, K; static int n; static int answer; static String[] words; static int[] nums; static HashSet hs; static int hsSize; static Integer[] num; public static boolean checkWord(String s) { for(int i = 0; i < s.length(); i++) { if(!alpha[s.charAt(i)-'a']) { return false; } } return true; } public static void select(int cnt, int index) { if(cnt == K) { int ret = 0; for(int i = 0; i < n; i++) { if(checkWord(words[i])) { ret++; } } answer = Math.max(answer, ret); return; } for(int i = index; i < hsSize; i++) { if(!alpha[num[i]]) { alpha[num[i]] = true; select(cnt + 1, i + 1); alpha[num[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()); if(K < 5) { System.out.println(0); } else if(K == 26) { System.out.println(N); } else { words = new String[N]; n = 0; int count = 0; HashSet HS; hs = new HashSet<>(); for(int i = 0; i < N; i++) { String s = br.readLine(); HS = new HashSet<>(); s = s.substring(4, s.length()-4); int len = s.length(); if(len == 8) { //antatica인 경우와, antic으로만 된 경우 count++; continue; } for(int j = 0; j < len; j++) { HS.add(s.charAt(j)-'a'); } int cnt = HS.size(); if(cnt == 5) { //antic으로만 이루어진 경우 count++; continue; } if(cnt > K) continue; //필요한 글자수가 K보다 클 때 for(int j = 0; j < len; j++) { //직접확인해봐야하는 경우 int num = s.charAt(j) - 'a'; if(!alpha[num]) { hs.add(num); } } words[n++] = s; } answer = 0; hsSize = hs.size(); num = hs.toArray(new Integer[hsSize]); if(hsSize + 5 <= K) { System.out.println(words.length + count); } else { select(5, 0); System.out.println(answer+count); } } } }

제출 #20621

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: