[PS] BOJ16508 전공책 ( DFS ) With JAVA

16508번: 전공책

 

 

◎문제풀이 

 

타이틀을 완성하도록 전공책을 선택할 때 가장 적은 비용을 고르는 문제이다.

 

나는 DFS 풀이를 발상하기는 했지만 완전탐색을 어떤 방식으로 할지 구현하지 못했다. 그러나 굉장히 단순한 풀이였다. 오히려 너무 단순해서 풀이방식을 떠올리지 못한 것 같다. 

• 전공책을 선택할 수 있고
• 전공책을 선택 안 할 수도 있다.
• 선택하는 경우와 안 하는 경우로 DFS 탐색하며, 타이틀을 완성 여부를 체크하고 비용의 최소값을 구하면 된다.

◎ 코드

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

public class Main{

    static int n;
    static Book[] books;
    static int[] alphabets;
    static int[] countWord;
    static int ans = Integer.MAX_VALUE;

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

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

        String str = br.readLine();
        n = Integer.parseInt(br.readLine());

        books = new Book[n];
        alphabets = new int['Z'-'A'+1];
        countWord = new int['Z'-'A'+1];

        for(char ch : str.toCharArray()){
            alphabets[ch-'A']++;
        }

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

            int price = Integer.parseInt(st.nextToken());
            String title = st.nextToken();

            books[i] = new Book(price,title);
        }

        dfs(0,0);

        if(ans==Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(ans);

    }

    public static void dfs(int index, int sum){
        if(index == n){
            if(check()){
                ans = Math.min(ans,sum);
            }
            return;
        }

        // 책을 선택한 경우
        for(int i=0;i<books[index].title.length();i++){
            char ch = books[index].title.charAt(i);
            countWord[ch-'A']++;
        }

        dfs(index + 1, sum + books[index].price);

        for(int i=0;i<books[index].title.length();i++){
            char ch = books[index].title.charAt(i);
            countWord[ch-'A']--;
        }

        // 책을 선택하지 않은 경우
        dfs(index +1,sum);
    }

    public static boolean check(){

        for(int i=0;i<alphabets.length;i++){
            if(alphabets[i] > countWord[i]) return false;
        }

        return true;

    }

    public static class Book{
        int price;
        String title;

        public Book(int price, String title){
            this.price = price;
            this.title = title;
        }
    }
}