자바(Java) 백준 1062 가르침 풀이

문제

https://www.acmicpc.net/problem/1062

1062번: 가르침

풀이

저는 dfs와 조합으로 문제를 풀었습니다.

• 학생들이 어떤 알파벳을 배웠는지 알 수 있는 aplhaArr라는 boolean 배열을 만들어줍니다.
• 문제에서 anta, tica 두개의 접두사와 접미사가 단어 안에 무조건 들어가야합니다. 따라서 a, n, t, i, c 5개의 알파벳은 학생들이 배우지 않는다면 어떤 단어도 읽을 수가 없습니다. 따라서 k가 5개 미만이라면 어떤 단어도 읽을 수 없으므로 0을 출력해야 합니다.
• 만약 k가 5 이상이라면 a, n, t, i, c 5개의 알파벳은 필수적으로 알아야하므로 aplhaArr에 true로 먼저 체크해줍니다.
• 이제 dfs() 메소드를 호출하여 26개의 알파벳중에 학생들이 배운 k 개의 알파벳의 조합을 구합니다.
• k개의 알파벳을 배웠다면 countWord() 메소드에서 학생들이 읽을 수 있는 단어의 개수를 구합니다.
• 위 과정을 통해 학생들이 읽을 수 있는 단어의 최대값을 구합니다.

코드

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

public class Main {

    static int n;
    static int k;
    static String[] words;
    static boolean[] alphaArr = new boolean[26];
    static int max = 0;

    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());
        words = new String[n];

        for (int i = 0; i < n; i++) {
            words[i] = br.readLine();
        }

        // anta, tica에 들어가는 5개의 알파벳은 항상 사용되므로 true로 처리해줍니다.
        alphaArr['a' - 'a'] = true;
        alphaArr['n' - 'a'] = true;
        alphaArr['t' - 'a'] = true;
        alphaArr['i' - 'a'] = true;
        alphaArr['c' - 'a'] = true;

        if (k < 5) {
            // k가 5 미만인 경우에는 모든 단어를 완성할 수 없으므로 0을 출력합니다.
            System.out.println(max);
        } else {
            dfs(0, 0);
            System.out.println(max);
        }
    }

    // 학생들에게 가르칠 k개의 알바벳의 조합을 구합니다.
    public static void dfs(int idx, int cnt) {
        // 학생들이 k개의 알파벳을 배웠으므로 읽을 수 있는 단어의 개수를 구합니다.
        if (cnt + 5 == k) {
            countWord();
            return;
        }

        for (int i = idx; i < 26; i++) {
            if (alphaArr[i]) {
                continue;
            }

            alphaArr[i] = true;
            dfs(i + 1, cnt + 1);
            alphaArr[i] = false;
        }
    }

    // 학생들이 읽을 수 있는 단어의 개수를 구합니다.
    public static void countWord() {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            char[] alphas = words[i].toCharArray();
            boolean flag = true;
            for (char c: alphas) {
                if (!alphaArr[c - 'a']) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                cnt++;
            }
        }
        max = Math.max(max, cnt);
    }
}