[JAVA]백준 1062번: 가르침

 

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

1062번: 가르침

1. 문제 설명

 

남극의 단어는 "anta"로 시작되고 "tica"로 끝난다. 김지민 선생님이 K개의 글자를 가르칠 수만 있다고 할 때, 남극의 단어 N개 중 학생들이 읽을 수 있는 단어의 최댓값을 구하는 문제.

 

2. 풀이

 

조합과 브루트포스 알고리즘으로 풀 수 있다.

 

비트 마스킹으로 풀면 더 빨리 풀 수 있는데 아래 코드에서는 배열을 사용하여 현재 배운 단어가 무엇인지 체크했다.

 

남극의 모든 단어는 anta, tica로 끝나기 때문에 필수적으로 a, n, t, i, c 가 들어간다.

 

따라서 선생님이 알려줄 수 있는 글자의 개수 K가 5보다 작으면 학생들은 읽을 수 있는 문자가 없으므로 0을 출력하면 된다.

 

5 이상인 경우 전체 21개의 알파벳(a,n,t,i,c 제외) 중에서 K-5개의 조합을 생성, 해당 조합에 대해 학생들이 읽을 수 있는 단어의 개수를 세어 최댓값을 출력하면 된다.

 

이렇게 해도 시간 초과가 발생하지 않는데 계산해 보면 최악의 경우

 

21 C10 * 50 (단어의 개수) * 7 (단어의 길이 : 단어의 길이 15 - 필수 단어 길이 8) = 123,450,600 이기에 충분히 1초 안에 가능하다.

 

3. 코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    public static int N, K;
    public static ArrayList<ArrayList<Character>> word = new ArrayList<>();
    public static boolean[] learn = new boolean[26];

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        String line;

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());


        // 배울수 있는 단어가 5개 미만이면 배울 수 없음.
        if (K < 5) {
            System.out.println("0");
            return;
        }

        // a, n, t, i, c 배움
        K -= 5;

        learn['a' - 'a'] = true;
        learn['c' - 'a'] = true;
        learn['n' - 'a'] = true;
        learn['t' - 'a'] = true;
        learn['i' - 'a'] = true;

        for (int x = 0; x < N; x++) {
            line = br.readLine();

            word.add(new ArrayList<>());

            for (int y = 0; y < line.length(); y++) {
                if(!learn[line.charAt(y)-'a'])
                    word.get(x).add(line.charAt(y));
            }
        }


        System.out.println(max_word(0, 0));

    }

    public static int max_word(int idx,int learn_idx) {

        // K개 다 선택
        if (K == idx) {
            // 단어 읽을 수 있는거 체크
            return readWord();
        }

        // 초과
        if(learn_idx==26)
            return 0;

        int ret = 0;

        //배우지 않은 단어이면
        if (!learn[learn_idx]) {
            // 이번 꺼 읽을 수 있게 함.
            learn[learn_idx] = true;
            ret = Math.max(ret, max_word(idx + 1, learn_idx + 1));
            learn[learn_idx] = false;
        }

        // 이번꺼 패스함.

        ret = Math.max(ret, max_word(idx, learn_idx + 1));

        return ret;

    }

    // 몇개의 단어 배울 수 있는지 체크
    public static int readWord() {
        boolean flag = true;

        int sum = 0;

        for (int x = 0; x < N; x++) {
            int size = word.get(x).size();

            flag = true;

            for (int y = 0; y < size; y++) {
                if (!learn[word.get(x).get(y) - 'a']) {
                    flag = false;
                    break;
                }
            }

            if(flag)
                sum++;
        }

        return sum;
    }




}