[boj] 백준 16508 전공책 (Java) - 완전탐색

[문제]

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

16508번: 전공책

 

[풀이]

정석적인 완전탐색 문제~

전공책을 선택하는 경우, 선택하지 않는 경우 2가지에 대해 모두 dfs를 돌려준다.

전공책을 선택하는 경우 해당 전공책의 포함된 모든 알파벳들을 1씩 증가시켜 준다.

모든 전공책에 대한 선택이 끝난 후, 선택된 전공책들에 포함된 알파벳들의 select[] 값이 만들고자 하는 문자열의 알파벳들인 count[] 보다 작은 값이 존재한다면 불가능한 조합이므로 false를 반환한다.

true라면 가격의 합을 가장 작은 값으로 갱신해준다.

 

전공책을 선택하지 않는 경우라면 이전에 증가시켰던 select[] 값을 다시 원상복구 시킨 후 dfs()를 호출.

 

[코드]

 

package 브루트포스;

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

public class boj_16508_전공책 {
    static String t;
    static int n;
    static int answer = Integer.MAX_VALUE;
    static int[] count;
    static int[] select;
    static boolean[] visited;
    static int[] price;
    static String[] book;
    public static void main(String[] args) throws Exception{
        //가장 적은 비용으로 민호가 원하는 단어를 만들기 위해서. 가장 적은 가격의 합 출력

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        t = br.readLine();
        n = Integer.parseInt(br.readLine());

        StringTokenizer st;
        price = new int[n];
        book = new String[n];
        count = new int[26];
        select = new int[26];

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

        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            price[i] = Integer.parseInt(st.nextToken());
            book[i] = st.nextToken();
        }

        dfs(0, 0);

        System.out.println((answer==Integer.MAX_VALUE) ? -1 : answer);
    
    }

    public static void dfs(int depth, int sum){
        if(depth==n){
            //n개의 전공책에 대한 선택이 모두 끝나면
            if(check()){
                answer = Math.min(answer, sum);
            }
            return;
        }

        //depth번째 전공책을 선택하는 경우
        for(int i=0; i<book[depth].length(); i++){
            select[book[depth].charAt(i)-'A']++;
        }
        dfs(depth+1, sum+price[depth]);

        //depth번째 전공책을 선택하지 않는 경우
        for(int i=0; i<book[depth].length(); i++){
            select[book[depth].charAt(i)-'A']--; //원상 복구
        }
        dfs(depth+1, sum);
    }
    
    public static boolean check(){
        for(int i=0; i<26; i++){
            if(count[i] > select[i]) return false;
        }

        return true;
    }
}

 

- 처음 짰던 코드. 50%에서 틀렸다고 나오는데 이유를 모르겠다..보류

 

package 브루트포스;

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

public class boj_16508_전공책 {
    static String t;
    static int n;
    static int answer = Integer.MAX_VALUE;
    static boolean[] visited;
    static int[] price;
    static String[] book;
    public static void main(String[] args) throws Exception{
        //가장 적은 비용으로 민호가 원하는 단어를 만들기 위해서. 가장 적은 가격의 합 출력

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        t = br.readLine();
        n = Integer.parseInt(br.readLine());

        StringTokenizer st;
        price = new int[n];
        book = new String[n];
        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            price[i] = Integer.parseInt(st.nextToken());
            book[i] = st.nextToken();
        }


        for(int i=1; i<=n; i++){
            //i권의 전공책 선택 
            visited = new boolean[n];

            int[] comb = new int[i];
            dfs(0, i, 0, comb, 0);

            if(answer!=Integer.MAX_VALUE) break;
        }

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

    public static void dfs(int depth, int end, int idx, int[] comb, int sum){
        if(depth==end){
            //i권의 전공책 조합을 선택, 원하는 글자 t를 만들 수 있다면
            if(check(comb)){
                if(sum < answer){
                    answer = sum;
                }
            }
            return;
        }

        for(int i=idx; i<n; i++){
            if(visited[i]) continue;

            visited[i] = true;
            comb[depth] = i;
            dfs(depth+1, end, i+1, comb, sum+price[i]);

            visited[i] = false;
        }
    }
    
    public static boolean check(int[] comb){
        char[] chars = t.toCharArray();
        boolean[] included = new boolean[t.length()];
        for(int c:comb){
            //해당 전공책들로 원하는 글자를 만들 수 있는지 확인
            String b = book[c];
            for(int i=0; i<b.length(); i++){
                char bc = b.charAt(i);
                for(int j=0; j<chars.length; j++){
                    if(included[j]) continue;
                    if(bc==chars[j]){
                        included[j] = true;
                        break;
                    }
                }
            }
        }

        for(int i=0; i<chars.length; i++){
            if(!included[i]) return false;
        }

        return true;
    }
}