백준 1062 가르침 (Gold4)

정답코드

import java.util.Scanner;

public class Main {
 
    static int n, k;
    static int max = Integer.MIN_VALUE;
    static boolean[] visited;
    static String[] word;
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        n = scan.nextInt();
        k = scan.nextInt();
        
        scan.nextLine();
        word = new String[n];
        
        //무조건 포함되는 단어는 굳이 계속 체크할 필요 없음
        for(int i = 0; i < n; i++) {
            String str = scan.nextLine();
            str = str.replace("anta", "");
            str = str.replace("tica", "");
            word[i] = str;
        }
		
        //알파벳 배열 선언
        visited = new boolean[26];
        
        //a,c,i,n,t는 무조건 포함 초기조건 주기 
        visited[0] = true;    //a
        visited[2] = true;    //c
        visited[8] = true;    //i
        visited[13] = true;   //n
        visited[19] = true;   //t
       
        
        backtracking(0, 0);
        if(max == Integer.MIN_VALUE)max = 0;
        System.out.println(max);
    }
    
    public static void backtracking(int alpha, int len) {
    	//5개는 이미 포함했으므로 k-5개만 확인
    	if(len == k-5) {
    		int cnt = 0;
    		
    		for(int i = 0; i < n; i++) {
    			boolean flag = true;
    			for(int j = 0; j < word[i].length(); j++) {
    				if(visited[word[i].charAt(j)-'a']==false) {
    					flag = false;
    					break;
    				}
    			}
    			if(flag == true)cnt++;
    		}
    		max = Math.max(max, cnt);
    	}
        
        //조합의 수로 사용가능한 단어 확인 
        for(int i = alpha; i < 26; i++) {
            if(visited[i] == false) {
                visited[i] = true;
                backtracking(i, len + 1);
                visited[i] = false;
            }
        }
    }
}

전략

• 앞 뒤로 남극글자에 포함되는 5개 단어는 무조건 포함되어야 한다

• 알파벳 배열을 선언해서 포함하는지, 포함하지 않는지를 반별한다.

• K개의 문자를 받으면 K-5개의 추가 문자를 확인, if K < 5이면 아무 글자도 만들 수 없다