[백준 1062] 가르침

문제 링크: https://www.acmicpc.net/problem/1062

---

풀이

조합과 브루트포스를 이용한 문제였다. 재귀의 깊이와 주어지는 단어의 개수 N을 고려하면 브루트포스가 가능한 문제라는 걸 알 수 있다. 모든 경우의 수를 진행하며 읽을 수 있는 단어의 수를 최댓값으로 갱신해주면 된다.

 

• 입력받은 K의 값이 5보다 작으면 0을 출력하고 프로그램을 종료한다.
  단어를 읽기 위해서는 a, c, i, n, t 적어도 5개의 글자를 가르쳐야 하는데 가르칠 수 있는 글자가 5보다 작으면 아무 단어도 읽을 수 없다.
• 접두어와 접미사는 미리 제거한다.
  a, c, i, n, t는 반드시 가르쳐야 하는 단어이기 때문에, 미리 가르쳤다고 가정하고 조합을 수행할 것이다. 접두어와 접미사를 replace()를 이용하여 제거해주면 단어의 길이를 줄일 수 있다.
• 가르친 글자의 수가 K-5개가 되면 재귀를 종료한다.
  조합을 진행하며 a, c, i, n, t를 제외하고 가르칠 글자들을 다 골랐다면, 읽을 수 있는 단어의 개수를 세고, 최댓값을 갱신한다.

---

전체 코드

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

public class Main_1062_가르침 {
    static int N, K, M = 26, answer = 0;
    static String[] words;
    static boolean isTeached[];
    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());
        K = Integer.parseInt(st.nextToken());

        if(K<5) {
            System.out.println(0);
            System.exit(0);
        }

        words = new String[N];
        isTeached = new boolean[M];

        for (int i=0; i<N; i++) {
            words[i] = br.readLine();
            words[i].replace("anta", "");
            words[i].replace("tica", "");
        }

        teachVitalAlphabet();
        teach(0, 0);

        System.out.println(answer);
    }

    static void teach(int cnt, int start) {
        if(cnt==K-5) {
            answer = Math.max(answer, countReadableWord());
            return;
        }
        for (int i=start; i<M; i++) {
            if(isTeached[i]) continue;
            isTeached[i] = true;
            teach(cnt+1, i+1);
            isTeached[i] = false;
        }
    }

    static void teachVitalAlphabet() {
        isTeached['a'-'a'] = true;
        isTeached['c'-'a'] = true;
        isTeached['i'-'a'] = true;
        isTeached['n'-'a'] = true;
        isTeached['t'-'a'] = true;
    }

    static int countReadableWord() {
        int result = 0;

        for (int i=0; i<N; i++) {
            boolean readable = true;
            for (int j=0; j<words[i].length(); j++) {
                int idx = words[i].charAt(j) - 'a';
                if(!isTeached[idx]) {
                    readable = false;
                    break;
                }
            }
            if(readable) result++;
        }

        return result;
    }
}

 

처음에는 단어에 나오지 않는 글자들은 이미 가르친 단어로 처리해두려고 했는데, 결과적으로 가르친 글자 수 cnt가 K-5개가 될 수 없기 때문에 틀렸습니다를 받았다. (cnt는 isTeached가 false에서 true로 바뀔 때 +1이 되는 값이기 때문이다.)