문제 1062번

소스코드

import java.io.*;
import java.util.*;
public class boj1062 {
    static int N, K;
    static int max = 0;
    static boolean visit[] = new boolean[26];
    static String[] sArr;
    public static void dfs(int start, int count) {
        if(count == K) {
            int num = 0;
            for(int i=0; i<sArr.length; i++) {
                boolean flag = true;
                for(int j=0; j<sArr[i].length(); j++) {
                    if(!visit[sArr[i].charAt(j) - 97]) {
                        flag = false;
                        break;
                    }
                }
                if(flag)	num ++;
            }
            max = Math.max(max, num);
            return;
        }
        for(int i=start; i<26; i++) {
            if(!visit[i]) {
                visit[i] = true;
                dfs(i, count + 1);
                visit[i] = false;
            }
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        sArr = new String[N];
        if(K<5) {
            System.out.println("0");
            return;
        }
        else if(K==26) {
            System.out.println(N);
            return;
        }
        else {
            for(int i=0; i<N; i++) {
                String str = bf.readLine();
                sArr[i] = str.substring(4, str.length()-4);
            }
            K -= 5;
            visit['a' - 97] = true;
            visit['n' - 97] = true;
            visit['t' - 97] = true;
            visit['i' - 97] = true;
            visit['c' - 97] = true;
            dfs(0, 0);
            System.out.println(max);
        }
        bf.close();
    }
}

풀이 접근

1. 모든 단어는 anta로 시작하고 tica로 끝난다고 한다. 그렇다면 최소 5개 이상의 단어를 알아야 읽을 수 있는 숫자가 존재한다는 의미로 볼 수 있다.
2. 추가로 k가 26이라면, 모든 알파벳을 배웠다는 뜻으로 주어진 단어 모두를 읽을 수 있다.
3. 나머지 경우를 계산하기 위해서는 DFS를 통한 완전탐색을 구현하기로 하였다.
4. 이미 5개의 알파벳이 존재하기 때문에, visited배열에 해당 5개의 알파벳의 위치에 true로 바꿔주고, K -=5를 해준 뒤 dfs 탐색을 돌리면서 최대값을 계속 초기화해 준다.

문제 핵심

• 백 트래킹
• 브루트포스 알고리즘