백준 1062 가르침

남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.

남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.

K가 21보다 작거나 같은 소문자 개수만큼이다

21CK 의 시간복잡도를 가지고 있다고 생각했다(조합)
a, c를 배우거나 c,a 를 배우거나 같으니까

조합을 사용하여 단어를 배울 수 있는 최대 개수를 갱신해주었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int limit;
    static int N;
    static boolean visited[];
    static int max = Integer.MIN_VALUE;
    static String record[];
    static String string[];
    static String alpha[] = {"a", "b", "c", "d", "e", "f","g","h", "i","j","k","l","m", "n","o","p","q","r","s","t","u","v","w","x","y","z"};
    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());
        int K = Integer.parseInt(st.nextToken());

        if(K < 5) {
            System.out.println(0);
            return;
        }
        if(K == 26) {
            System.out.println(N);
            return;
        }

        visited = new boolean[26];

        // 학습할 수 있는는 숫자
        limit = K - 5;
        record = new String[limit];
        string = new String[N];
        for(int i = 0; i < N; i++) {
            String s = br.readLine();
            s = s.replaceAll("[antic]","");

            s = change(s);

            string[i] = s;
        }
        Arrays.sort(string, (e1, e2) -> e1.length() - e2.length());


        DFS(0, 0);
        System.out.println(max);
    }
    static String change(String s ) {
        int sLen = s.length();
        String result = "";
        for(int i = 0; i < sLen; i++) {
            if(s.indexOf(s.charAt(i)) == i) result+=s.charAt(i);
        }
        return result;
    }

    static void DFS(int depth, int start ) {
        if(depth == limit) {
            int cnt = 0;

            for(int i = 0; i < N; i++) {
                String s = string[i];
                int sLen = s.length();
                // 개수 새기
                if(limit < sLen) {
                    break;
                }
                boolean flag = false;
                if(limit == sLen) {
                    for(int j = 0;  j < limit; j++) {
                        if(!s.contains(record[j])) {
                            flag = true;
                            break;
                        }
                    }
                    if(!flag) {
                        cnt++;
                    }
                } else if(limit > sLen) {
                    int sCnt = 0;
                    for(int j = 0;  j < limit; j++) {
                        if(s.contains(record[j])) {
                            sCnt++;
                        }
                    }
                    if(sCnt == sLen) {
                        cnt++;
                    }

                }



            }
            if(max < cnt) {
                max = cnt;
            }

            return;
        }

        for(int i = start; i < 26; i++) {
            if(i == 0 || i == 2 || i == 8 || i == 13 || i == 19 ) {
                continue;
            }
            record[depth] = alpha[i];
            DFS(depth + 1, i + 1);
        }

    }

}