[백준_16508번] 전공책

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

16508번: 전공책

[문제]

 곧 졸업을 앞둔 민호는 대학교 생활 동안 구매만 해놓고 한 번도 펴보지 않은 전공책에 먼지가 쌓여 있는 것을 보고는, 이 책들을 어떻게 처리해야 할지 고민 중이다. 열심히 고민한 끝에 민호는 결국 전공책을 모두 버리기로 마음먹었다. 하지만 그냥 버리기엔 심심한 민호는 전공책 제목에 있는 글자들을 오려서 단어 만들기 놀이를 하려고 한다. 단어 만들기 놀이는 아래 예시와 같다.

 

• 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는 항상 대문자이다.

 

[코드]

import java.util.*;

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

public class BaekJoon_16508 {
	static ArrayList<Book_16508> arr=new ArrayList<>();
	static String str;
	static int[] count=new int[26];
	static int[] select=new int[26];
	static int n,min=Integer.MAX_VALUE;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		str=sc.next();
		n=sc.nextInt();
		
		// 만들고 싶은 단어의 구성된 알파벳의 배열 값을 1로 변경
		for(int i=0;i<str.length();i++)
			count[str.charAt(i)-'A']++;
		
		for(int i=0;i<n;i++) {
			int price=sc.nextInt();
			String title=sc.next();
			
			arr.add(new Book_16508(price,title));
		}
		
		dfs(0,0);
		System.out.println(min==Integer.MAX_VALUE?-1:min);
	}
	
	static void dfs(int depth, int total) {
		// n개의 책을 모두 탐색했고, 알파벳을 모두 구했다면 최솟값 갱신
		if(depth==n) {
			if(check())
				min=Math.min(total, min);
			return;
		}
		
		/*
		 * 책을 선택하는 방법에는 두 가지가 있다.
		 * 현재 depth 번째의 책을 선택하느냐, 선택하지 않느냐 
		 */
		
		/*
		 * depth번째의 책을 선택한 경우 depth번째의 책의 제목을 구성하는
		 * 알파벳의 배열 값을 모두 1로 변경한 뒤 depth를 1 증가, 
		 * 총액을 depth번째의 책 가격만큼 증가키기고 재귀호출 한다.
		 */
		for(int i=0;i<arr.get(depth).title.length();i++)
			select[arr.get(depth).title.charAt(i)-'A']++;
		dfs(depth+1,total+arr.get(depth).price);
		
		/*
		 * depth번째의 책을 선택하지 않는 경우는 
		 * 이전에 증가시켰던 배열 값을 모두 초기화 시킨 후, 총액은 이전의 값을 유지한 채로 재귀호출 한다.
		 */
		for(int i=0;i<arr.get(depth).title.length();i++)
			select[arr.get(depth).title.charAt(i)-'A']--;
		dfs(depth+1,total);
	}
	
	// 만들고 싶은 단어의 모든 알파벳이 나왔는지 확인하는 함수
	static boolean check() {
		for(int i=0;i<26;i++)
			if(count[i]>select[i])
				return false;
		return true;
	}
}

 

[고찰]

 주어지는 책의 개수가 1~16개 사이이기 때문에 이번 문제는 백트래킹과 완전탐색을 사용하여 해결할 수 있다. 책을 고르는 경우는 2가지가 있는데 현재 책을 선택할 것이냐, 선택하지 않을 것이냐이다. 현재 책을 선택했다면 책의 제목을 이루는 알파벳의 배열 값을 모두 1로 변경해주고 해당 책의 금액만큼 총액을 증가시켜 재귀호출을 진행하고, 현재 책을 선택하지 않는다면 깊이만 1 증가시키고 재귀호출을 한다. n개의 책을 모두 탐색했다면 만들고자 하는 단어를 구성하는 알파벳이 모두 나왔는지의 여부에 따라 최솟값을 갱신 하면 된다.