[Java] BOJ 16508 전공책

문제 

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

• 민호는 전공책 제목에 있는 글자들을 오려서 단어 만들기 놀이를 하려고 한다.
• 단어 만들기 놀이는 아래 예시와 같다.
  • 1번 책 : COMPUTERARCHITECTURE (35,000원)
  • 2번 책 : ALGORITHM (47,000원)
  • 3번 책 : NETWORK (43,000원)
  • 4번 책 : OPERATINGSYSTEM (40,000원)
  • 만약 민호가 만들고 싶은 단어가 ALMIGHTY라고 하면, 위 4개의 책 중, 1번 책에서 A를, 2번 책에서 L, M, I, G, H, T를, 4번 책에서 Y를 오려내어 원하는 단어를 만들 수 있다.
  • 이때 드는 비용은 1번, 2번, 4번 책 가격의 합인 122,000원이다.
  • 만약 ANT라는 단어를 만들고 싶다고 하면, 2번 책에서 A를, 3번 책에서 N, T를 오려내어 원하는 단어를 만들 수 있다. 이때 드는 비용은 2번과 3번 책 가격을 합하여 90,000원이다.
  • 그런데, ANT라는 단어에서 A를 2번 책에서 오려내지 않고, 4번 책에 있는 A를 오려낼 수도 있다. 만약 4번 책에서 A를 오려냈을 때 드는 비용은 3번과 4번 책 가격을 합하여 83,000원으로 2번과 3번 책을 고른 비용보다 작다.
  • 하지만, 4번 책에는 ANT가 모두 포함되어 있으므로, 4번 책만 선택했을 때 드는 비용이 40,000원이다.
  • 이는 ANT라는 단어를 만들기 위해서 가장 적은 비용이다.
• 민호는 가장 적은 비용으로 자신이 원하는 단어를 만들려면 어떤 전공책들을 선택해야 하는지 궁금했다. 
• 민호를 도와 각 전공책의 가격과 제목이 주어졌을 때, 가장 적은 비용으로 민호가 원하는 단어를 만들기 위해서 어떤 전공책을 선택해야 하는지 알아보자.
• 첫 번째 줄에는 민호가 만들고자 하는 단어를 의미하는 문자열 T (1 ≤ |T| ≤ 10)가 주어진다. T는 항상 대문자이며, |T|는 문자열 T의 길이를 의미한다.
• 두 번째 줄에는 민호가 가진 전공책의 개수를 의미하는 정수 N (1 ≤ N ≤ 16)이 주어진다.
• 다음 N개의 각 줄에는 전공책 가격을 의미하는 정수 Ci (10,000 ≤ Ci ≤ 100,000)와 제목을 의미하는 문자열 Wi (1 ≤ |Wi| ≤ 50)가 주어진다. Wi는 항상 대문자이다.
• 민호가 원하는 단어 T를 만들기 위해서 선택해야 하는 전공책의 가장 적은 가격의 합을 출력한다. 만약 단어를 만들 수 없다면 -1을 출력한다.

아이디어

• 우선 책 가격과 제목을 입력받고 DFS를 통해 책의 조합을 짰다.
• 그리고 해당 책 조합의 제목들에서 HashMap을 활용하여 글자와 해당 글자의 갯수를 저장한다.
• 그리고 찾아야되는 문자열에 있는 문자와 해당 문자의 갯수를 HashMap에 저장한다.
• 그리고 찾아야되는 문자를 key로 기준으로 책 조합의 제목들의 글자와 글자수를 저장한 HashMap에서 value 값을 찾고, 찾아야되는 문자열의 문자와 갯수를 저장한 HashMap에 저장된 value보다 작거나 해당 key값이 없으면 해당 책 조합에서 찾아야되는 문자열을 찾을 수 없다는 뜻이므로 넘어간다.
• 만약 찾을 수 있다면 해당 문자열을 찾을 수 있다는 뜻이므로 최솟값을 갱신할 수 있을 경우, 최솟값을 갱신한다.  

겪은 시행착오

• 뭔가.. 문제를 너무 어렵게 푼거 같다... 좀 쉽게 푸는 방법이 있었을 것 같은데... 찾아봐야겠다..

쉬운문제였던 것 같은데 어렵게 오래 푼거 같아서 슬프다..ㅜㅜ 더 정진하자..ㅜㅜㅜ

코드

import java.io.*;
import java.util.*;

public class BOJ16508 {

    static public int[] cost;
    static public boolean[] visited;
    static public String[] books;
    static public int N;
    static public String s;
    static public int result;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 만들 글자
        s = br.readLine();

        // 책 수
        N = Integer.parseInt(br.readLine());

        // 가격 저장할 배열
        cost = new int[N];
        // 가격이랑 책 이름을 저장할 배열
        books = new String[N];
        // 책 조합을 만들 때 쓸, 방문 여부
        visited = new boolean[N];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            // 가격
            cost[i] = Integer.parseInt(st.nextToken());
            // 책 이름
            books[i] = st.nextToken();
        }

        // 결과값 초기화
        result = Integer.MAX_VALUE;

        // 책 조합을 통해 최소 비용을 찾음
        for (int i = 1; i <= N; i++) {
            int[] arr = new int[i];
            DFS(0, i, arr);
        }

        // 결과값이 갱신되지 않았다면 -1 출력
        if (result == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(result);
        }
    }

    // DFS 탐색
    public static void DFS(int depth, int limit, int[] pri) {
        if (depth == limit) {
            // 선택한 책 조합의 가격과 글자 매칭 수행
            checkWords(pri);
            return;
        }

        // 중복 조합 방지 (현재 depth의 이전 인덱스보다 큰 인덱스만 탐색)
        for (int i = (depth == 0) ? 0 : pri[depth - 1] + 1; i < N; i++) {
            if (!visited[i]) {

                visited[i] = true;
                pri[depth] = i;

                DFS(depth + 1, limit, pri);

                visited[i] = false;
            }
        }
    }

    // 선택한 책 조합으로 최소 비용 찾기
    public static void checkWords(int[] pri) {
        // 찾아야 하는 문자와 갯수를 저장할 HashMap
        HashMap<Character, Integer> targetCount = new HashMap<>();

        // 찾아야하는 문자열에서 글자를 키로 하여 그 문자의 갯수만큼 value값을 갱신
        for (char c : s.toCharArray()) {
            targetCount.put(c, targetCount.getOrDefault(c, 0) + 1);
        }

        // 조합된 책들의 문자와 갯수를 저장할 HashMap
        HashMap<Character, Integer> currentCount = new HashMap<>();

        // 책의 총 가격
        int totalPrice = 0;

        // 조합된 책 배열의 총 가격을 계산하고
        for (int i : pri) {
            totalPrice += cost[i];

            // 해당 제목들에 있는 문자를 key값으로 하여 그 문자의 개수를 value로 저장
            for (char c : books[i].toCharArray()) {
                // 해당 문자가 이미 HashMap에 key값으로 있으면 기준 value값에 1을 더한 값을
                // value값으로 저장하고 없다면 1을 저장
                currentCount.put(c, currentCount.getOrDefault(c, 0) + 1);
            }
        }

        // 목표 글자가 모두 포함되어 있는지 확인
        boolean canMake = true;

        for (char key : targetCount.keySet()) {
            // 만약 찾아야되는 문자의 갯수가
            // 책 제목의 조합에서 찾은 문자의 갯수보다 작거나 해당 문자를
            // key 값으로 찾을 수 없다면
            if (currentCount.getOrDefault(key, 0) < targetCount.get(key)) {
                // 목표 글자를 모두 못 찾으므로 false로 변환
                canMake = false;

                break;
            }
        }


        // 목표 문자를 만들 수 있다면, 가격 갱신
        if (canMake) {
            result = Math.min(result, totalPrice);
        }
    }
}