백준 1062번 : 가르침 풀이(Java) - 브루트포스

www.acmicpc.net/problem/1062

1062번: 가르침

Solution

이 문제는 조합 + 브루트포스로 풀 수 있다. 해법은 다음과 같다.

1. 가르칠 수 있는 문자가 K개로 한정되어 있으므로, a~z 중에 어떤 문자를 가르칠 지 정해야 한다. -> 바로 조합임을 알 수 있다.
2. 그럼 주어진 단어들을 읽을 수 있냐는 간단하다. 단어의 0번 알파벳부터 끝 알파벳까지, 가르친 적 없는 문자가 하나라도 있다면 읽을 수 없으므로 갯수에 포함하지 않고, 다 읽을 수 있다면 답을 더해준다.
3. 모든 조합의 경우의 수에서, 읽을 수 있는 최대값을 구한다.

이다.

알파벳은 a부터 z까지 26개 이므로, 26개 중에 K개를 뽑으면 되겠다. 그렇게 푼게 맨 밑의 풀이, 2616ms 가 나왔다.

 

사실 첫 풀이를 제출할 때 시간초과가 날 줄 알았는데, 엄청나게 긴 시간이 나왔으므로 바로 떠오른 시간 줄이기 방법을 적용했다.

 

문제의 조건 중에,

• 남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다.

라는 게 있다. 즉, anta 와 tica 를 "반드시" 읽을 수 있어야 단어 전체를 읽어볼 수 있을까 말까한다는 뜻이다.

anta 와 tica 를 읽으려면 기본적으로 a, n, t, i, c 의 알파벳을 알아야 하므로, 이 5개는 기본으로 깔고 가자는 거다.

 

이는 곧, K 가 5 미만이라면(가르칠 수 있는 문자 갯수가 5 이하라면) 어떤 단어가 오든 아예 못 읽는다는 말이므로 조기 종료해주면 된다.

 

코드를 보면 금방 이해 될 것이다.

 

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    private static BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
    private static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    private static int N,K, answer;
    private static String[] words;
    private static boolean[] pickedChars;
    private static char[] defaults = new char[]{'a','c','n','t','i'};
    
    public static void main(String[] args) throws IOException {
        input();
        solve();
        bufferedReader.close();
        bufferedWriter.close();
    }

    private static void input() throws IOException {
        StringTokenizer nk = new StringTokenizer(bufferedReader.readLine());
        N = Integer.parseInt(nk.nextToken());
        K = Integer.parseInt(nk.nextToken());
        if(K < 5) { // 가르칠 수 있는 게 5개 미만이면 어차피 아무것도 못읽는다.
            System.out.println(0);
            System.exit(0);
        }
        K -= 5; // 디폴트로 뽑을 것이므로
        words = new String[N];
        for(int i = 0 ; i < N; i++) {
            String word = bufferedReader.readLine();
            words[i] = word;
        }
    }
    
    private static void solve() {
        makeCombination(0,0,new int[K]);
        System.out.println(answer);
    }
    
    private static void makeCombination(int start, int cnt, int[] picked) {
        if(cnt == K) {
            pickedChars = new boolean[26];
            setDefault();
            for(int i = 0 ; i < K; i++) {
                char c = (char)(picked[i] + 97);
                pickedChars[picked[i]] = true;
            }
            checkReadable();
            return;
        }
        for(int i = start; i < 26; i++) { // 0번부터 25번 까지(a부터 z까지)
            boolean alreadyPicked = false; // 미리 가르친 a,c,n,t,i 중에서 또 가르치면 낭비이므로,
            for(char aDefault : defaults) {
                if(aDefault-'a' == i) { // 만약 i 번이 이미 가르친 a,c,n,t,i 의 code값과 같다면
                    alreadyPicked = true; // 낭비임을 체크해준다.
                    break;
                }
            }
            if(alreadyPicked) { // 만약 낭비라면, 조합을 만들어줄 필요가 없다.
                continue;
            }
            picked[cnt] = i;
            makeCombination(i+1, cnt+1, picked);
        }
    }

    private static void setDefault() {
        for (char aDefault : defaults) {
            pickedChars[aDefault - 'a'] = true;
        }
        // a,c,n,t,i 를 미리 가르친다.
    }

    private static void checkReadable() {
        int sum = 0;
        for(int i = 0 ; i < N; i++) {
            boolean readable = true; // 해당 단어를 읽을 수 있는지
            for(int j = 0 ; j < words[i].length(); j++) {
                char c  = words[i].charAt(j); // 단어의 알파벳 하나하나 중에
                if(!pickedChars[(int)c - 97]) { // 안가르친게 있다면 
                    readable = false; // 읽을 수 없음을 체크해준다.
                    break;
                }
            }
            if(readable) { // 읽을 수 있다면 
                sum++; // 갯수를 더해주고
            }
        }
        answer = Math.max(answer, sum); // 최대값을 저장해준다.
    }
}