[JAVA] BOJ(백준) 1062 가르침

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

1062번: 가르침

 

문자열과 백트래킹 문제다.

 

모든 언어는 "anti"로 시작되고, "tica"로 끝난다.

모든 언어는 8글자 이상이고 15글자 이하다.

학생들은 K개의 글자로만 이루어진 단어만 읽을 수 있다.

 

즉, K개에 a, n, t, i, c은 필수로 포함된다.

a, n, t, i, c는 항상 포함되므로 별도로 확인할 필요가 없기 때문에

문자열을 입력 받을 때 앞뒤 고정 부분을 제거하고 저장한다.

 

K가 5보다 작다면 학생들은 어떤 단어도 읽을 수 없으므로 0이다.

어떤 글자를 배웠을 때 가장 많은 단어를 읽을 수 있는지 찾기 위해서는 백트래킹을 사용해야 한다.

백트래킹으로 배울 수 있는 글자의 수의 조합을 찾고, 이 조합으로 읽을 수 있는 단어의 수를 찾늗다.

모든 경우에서의 최대값을 찾아 출력한다.

 

주의해야 할 점은 조합이므로 백트래킹에서 조합을 찾을 때 현재 값의 다음 값부터 탐색을 시작해야 한다.

이 부분을 잘못 처리해서 시간초과가 났었다...

 

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

public class Main {

    static int n;
    static int m;
    static int res;
    static String[] arr;
    static boolean[] alpha;

    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());
        m = Integer.parseInt(st.nextToken());

        if (m < 5){
            System.out.println(0);
            return;
        }

        alpha = new boolean[26];

        alpha[0] = true;
        alpha[2] = true;
        alpha[8] = true;
        alpha[13] = true;
        alpha[19] = true;

        arr = new String[n];

        for (int i = 0; i < n; i++){
            arr[i] = br.readLine();
            arr[i] = arr[i].substring(4, arr[i].length() - 4);
        }

        study(1, 5);

        System.out.println(res);
    }

    public static void study(int cur, int cnt){
        if (cnt == m) {
            res = Math.max(res, check());
            return;
        }

        for(int i = cur; i < 26; i++){
            if (!alpha[i]){
                alpha[i] = true;
                study(i + 1, cnt + 1);
                alpha[i] = false;
            }
        }
    }

    public static int check(){
        int cnt = 0;
        for (String s : arr){
            int tmp = 0;
            for (int i = 0; i < s.length(); i++){
                if (!alpha[s.charAt(i) - 'a']){
                    break;
                }
                tmp++;
            }
            if (tmp == s.length()){
                cnt++;
            }
        }

        return cnt;
    }
}