백준 1062 가르침 (Java,자바)

jonghyukLee·2022년 10월 26일
0

이번에 풀어본 문제는
백준 1062번 가르침 입니다.

📕 문제 링크

❗️코드

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

public class Main {
    static int N,K;
    static boolean [] isLearned;
    static List<String> dic;
    static int answer;
    static int learnCount;
    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());
        isLearned = new boolean[26];
        // a, c, i, n, t는 기본으로 배워야함
        isLearned[0] = true;
        isLearned[2] = true;
        isLearned[8] = true;
        isLearned[13] = true;
        isLearned[19] = true;

        learnCount = K - 5;
        if (learnCount >= 0) {
            dic = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                String input = br.readLine();
                // anta, tica 자름
                String str = input.substring(4, input.length() - 4);
                dic.add(str);
            }
            dfs(0,0);
        }
        System.out.print(answer);
    }
    static void dfs(int start, int count) {
        if (count == learnCount) {
            answer = Math.max(answer, readDic());
            return;
        }
        for (int i = start; i < 26; i++) {
            if (!isLearned[i]) {
                isLearned[i] = true;
                dfs(i, count + 1);
                isLearned[i] = false;
            }
        }
    }
    static int readDic() {
        int tmp = 0;
        next : for (String str : dic) {
            int strLen = str.length();
            for (int i = 0; i < strLen; i++) {
                if (!isLearned[str.charAt(i) - 97]) continue next;
            }
            tmp++;
        }
        return tmp;
    }
}

📝 풀이

학생들에게 K개의 문자를 가르쳐, N개의 문자열 중 가장 많이 읽을 수 있는 경우를 구하는 문제입니다.
주어지는 문자열은 anta로 시작하고 tica로 끝난다는 규칙이 존재하기 때문에, 최소 a,c,i,n,t 5가지 문자는 무조건 가르쳐야 합니다.
따라서 K값이 5보다 작은 경우는 0을 출력해줍니다.
이외 경우에서는 가르칠 수 있는 모든 경우의 수를 고려하여 문자열을 읽을 수 있는 최댓값을 누적하여 최종 출력해주면 해결할 수 있습니다.

📜 후기

문제가 꽤나 복잡하게 설명되어 있는 것 같습니다ㅠ

profile
머무르지 않기!

0개의 댓글