백준 16508 - 전공책

Java

16508 번 - 전공책

문제

접근 방법

조합으로 책들 중 뽑을 수 있는 모든 경우의 수로 책을 뽑는다.

여기서 책의 개수는 16개 이며, 조합의 경우 16Cn (1 <= n <= 16)은 1억을 넘지 않으므로 시간 초과가 나지 않는다.

책들로 뽑을 수 있는 모든 조합의 책을 만들어야 하므로,
1개의 책을 뽑을 때 — nC1
2개의 책을 뽑을 때 — nC2
~~
n개의 책을 뽑을 때 — nCn

의 경우를 모두 조합으로 뽑아서 확인한다.

책의 조합을 하나 뽑을 때 마다, 그 책들을 통해 단어를 만들 수 있는지 판단하고,
만약 만들 수 있으면 그 책들의 가격의 합을 구하여 최소의 가격의 합을 구한다.

단어를 만들 수 있는지 판단하는 방법은, 각 인덱스가 A부터 Z를 나타내는 int 배열을 만들어
단어의 알파벳의 인덱스로 배열에 접근해 개수를 늘려 총 단어의 개수를 비교한다.

코드

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

public class Main {
	static int n, result;
	static int[] sel, words;
	static Book[] books;
	static String inStr;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk;
    	inStr = br.readLine();
    	n = stoi(br.readLine());
    	result = Integer.MAX_VALUE;
    	books = new Book[n];
    	words = new int[26];

    	// 만들 단어의 알파벳 수를 센다
    	int len = inStr.length();
    	int idx;
    	for(int i = 0; i < len; i++) {
    		idx = inStr.charAt(i) - 'A';
    		words[idx]++;
    	}

    	// 책을 입력 받는다
    	for(int i = 0; i < n; i++) {
    		stk = new StringTokenizer(br.readLine());
    		Book book = new Book(stoi(stk.nextToken()), stk.nextToken());
    		books[i] = book;
    	}

    	for(int i = 1; i <= n; i++) {
    		sel = new int[i];
    		DFS(0, i, 0);
    	}

    	if(result == Integer.MAX_VALUE)
    		System.out.println(-1);
    	else
    		System.out.println(result);
    	br.close();
	}

	static void DFS(int lv, int lim, int st) {
		if(lv == lim) {
			// 뽑은 책으로 단어를 만들 수 있는지 판단
			if(chkMakeWord(lim)) {
				int sum = 0;
				// 단어를 만들 수 있다면 뽑은 책 가격의 합을 구한다
				for(int i = 0; i < lim; i++) {
					sum += books[sel[i]].getPrice();
				}

				result = Math.min(result, sum);
			}
			return;
		}
		// 책의 개수만큼 반복
		for(int i = st; i < n; i++) {
			sel[lv] = i;
			DFS(lv + 1, lim, i + 1);
		}
	}

	private static boolean chkMakeWord(int lim) {
		boolean canMake = true;
		int[] wordInBooks = new int[26];
		String str;
		int idx, len;
		for(int i = 0; i < lim; i++) {
			str = books[sel[i]].getName();	// 뽑은 책 한권을 가져온다
			len = str.length();

			for(int j = 0; j < len; j++) {
				idx = str.charAt(j) - 'A';
				wordInBooks[idx]++;		// 책에 포함되어 있는 단어의 개수를 증가
			}
		}

		for(int i = 0; i < 26; i++) {
			// 만약 뽑은 책들에 있는 각 알파벳 종류의 총 개수보다 만들 단어의 알파벳의 개수가 많으면
			// 해당 책으로 단어를 만들 수 없다.
			if(wordInBooks[i] < words[i]) {
				return false;
			}
		}

		return canMake;
	}

	static class Book{
		int price;
		String name;
		public Book(int price, String name) {
			super();
			this.price = price;
			this.name = name;
		}
		public int getPrice() {
			return price;
		}
		public String getName() {
			return name;
		}
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }

}

총평

후기

DFS : 조합

부하 테스트 :

ABCDEFGHIJ
16
10000 ABCDEFGHIJKLNMOPQRSTUVWKYABCDEFGHIJKLNMOPQRSTUVWKY
10000 ABCDEFGHIJKLNMOPQRSTUVWKYABCDEFGHIJKLNMOPQRSTUVWKY
10000 ABCDEFGHIJKLNMOPQRSTUVWKYABCDEFGHIJKLNMOPQRSTUVWKY
10000 ABCDEFGHIJKLNMOPQRSTUVWKYABCDEFGHIJKLNMOPQRSTUVWKY
10000 ABCDEFGHIJKLNMOPQRSTUVWKYABCDEFGHIJKLNMOPQRSTUVWKY
10000 ABCDEFGHIJKLNMOPQRSTUVWKYABCDEFGHIJKLNMOPQRSTUVWKY
10000 ABCDEFGHIJKLNMOPQRSTUVWKYABCDEFGHIJKLNMOPQRSTUVWKY
10000 ABCDEFGHIJKLNMOPQRSTUVWKYABCDEFGHIJKLNMOPQRSTUVWKY
10000 ABCDEFGHIJKLNMOPQRSTUVWKYABCDEFGHIJKLNMOPQRSTUVWKY
10000 ABCDEFGHIJKLNMOPQRSTUVWKYABCDEFGHIJKLNMOPQRSTUVWKY
10000 ABCDEFGHIJKLNMOPQRSTUVWKYABCDEFGHIJKLNMOPQRSTUVWKY
10000 ABCDEFGHIJKLNMOPQRSTUVWKYABCDEFGHIJKLNMOPQRSTUVWKY
10000 ABCDEFGHIJKLNMOPQRSTUVWKYABCDEFGHIJKLNMOPQRSTUVWKY
10000 ABCDEFGHIJKLNMOPQRSTUVWKYABCDEFGHIJKLNMOPQRSTUVWKY
10000 ABCDEFGHIJKLNMOPQRSTUVWKYABCDEFGHIJKLNMOPQRSTUVWKY
10000 ABCDEFGHIJKLNMOPQRSTUVWKYABCDEFGHIJKLNMOPQRSTUVWKY

개선할 점