[백준 1062] 가르침(Java)

문제

www.acmicpc.net/problem/1062

풀이

백트래킹을 이용해 김지민 선생님께서 가르치시는 글자 집합들의 경우의 수를 다 구한 다음에 가장 많은 단어를 알 수 있는 경우를 구하면 된다.

K개의 글자를 모으면 단어들을 검사한다.
모든 단어의 개수에서 K개의 글자 말고 다른 글자도 섞여있는 단어의 개수를 빼주었다.
이렇게 구한 모든 경우의 수 중 최대값을 구하면 된다.

import java.io.IOException;
import java.util.*;
 
public class Main {
 
    public static void main(String args[]) throws IOException {
        Scanner scan = new Scanner(System.in);
        int a = scan.nextInt();
        int b = scan.nextInt();
 
        String[] words = new String[a];
        for(int i=0;i<a;i++){
            words[i] = scan.next();
        }
        System.out.println(solution(words, new boolean[26], 0, 0, b));
    }
    public static int solution(String[] words, boolean[] alpha, int cur, int count, int b){
        if(count==b){
            int sum = words.length;
            for(int i=0;i<words.length;i++){
                String curWord = words[i];
                for(int j=0;j<curWord.length();j++){
                    if(!alpha[(int)curWord.charAt(j)-97]){
                        sum--; break;
                    }
                }
            }
            return sum;
        }else{
            if(cur==26) return 0;
            alpha[cur] = true;
            int case1 = solution(words, alpha, cur+1, count+1, b);
            alpha[cur] = false;
            int case2 = solution(words, alpha, cur+1, count, b);
            return Math.max(case1, case2);
        }
    }
 
 
}