전공책16508

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

처음에 풀이를 안보고 어떻게 풀지 고민했을때는 방향이 전혀 잡히지 않았다

ANT 를 만들려고 한다면 ANT 글자를 어떻게 만들수 있을지에만 골똘히 집중했었다

답이 안나와서 다른 사람들의 풀이를 보고 책을 중심으로 풀어야 한다는것을 알게 되었다

그래서 책을 조합하는 것부터 만들어야 한다는 생각을 하였다. 0번책 1번책 2번책 3번책이 있다면 다음과 같은 탐색을 해야겠다고 생각하였다

책을 하나만 선택하는 경우
책을 두권 선택하는 경우
책을 세권 선택하는 경우
책을 네권 선택하는 경우...
모든 가능한 조합을 생성하도록 재귀함수를 작성하는 것부터 하였다. 마치 이진분할 트리를 DFS로 탐색하는 것과 같다

그리고 조합된 책으로 ANT 란 글자를 만들 수있는지 확인하고 만들수 있다면 책의 가격을 minPrice 로 저장하는 방식으로 풀었다

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

class Book
{
    String name;
    int price;

    int[] alphabetCnt;
    public Book(int price, String name) {
        this.name = name;
        this.price = price;

        alphabetCnt = new int[26];

        for(int i = 0; i < name.length(); ++i)
        {
            alphabetCnt[name.charAt(i) - 'A']++;
        }
    }
}

public class Main {

    static Book[] books;
    static int[] bookSelect;

    static boolean[] checked;

    static int N;

    static String T;

    static int[] needAlphabetCnt = new int[26];

    static int minPrice = Integer.MAX_VALUE;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        T = br.readLine();

        for(int i = 0; i < T.length(); ++i)
        {
            needAlphabetCnt[T.charAt(i) - 'A']++;
        }

        N = Integer.parseInt(br.readLine());
        books = new Book[N];
        bookSelect = new int[N];
        checked = new boolean[N];

        String[] input;
        for(int i = 0; i < N; ++i)
        {
            input = br.readLine().split(" ");
            books[i] = new Book(Integer.parseInt(input[0]), input[1]);
        }

        //책의 조합을 만드는 함수. 완전탐색. DFS
        search(0, 1);

        if(Integer.MAX_VALUE == minPrice)//실패!
        {
            System.out.println(-1);
        }
        else
            System.out.println(minPrice);
    }

    static void search(int depth, int targetDepth)
    {
        if(depth == targetDepth)
        {

//            for(int i = 0; i < depth; ++i)
//            {
//                System.out.print(bookSelect[i]);
//            }
//            System.out.println();

            canMakeSentence(depth);

            return;
        }

        for(int i = bookSelect[depth==0?depth:depth-1]; i < N; ++i)
        {
            if(checked[i])
                continue;

            checked[i] = true;
            bookSelect[depth] = i;
            search(depth+1, targetDepth);
            search(depth+1, targetDepth+1);
            checked[i] = false;
        }
    }

    static void canMakeSentence(int curDepth)
    {
        int[] alphabetCnt = new int[26];

        int price = 0;

        for(int i = 0; i < curDepth; ++i)
        {
            price += books[bookSelect[i]].price;
            for(int j =0; j < 26; ++j)
            {
                alphabetCnt[j] += books[bookSelect[i]].alphabetCnt[j];
            }

        }

        for(int i = 0; i < 26; ++i)
        {
            if(needAlphabetCnt[i] > alphabetCnt[i])
            {
                return;
            }
        }

        minPrice = Math.min(minPrice, price);

    }
}