[Silver 3] 16508 전공책

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

16508번: 전공책

 

이 문제는 조합을 이용한 완전 탐색을 이용해 해결해야한다.

선택한 책들의 알파벳 개수와 T의 알파벳 개수를 비교하여, 선택한 책들로 T를 만들 수 있다면 result를 갱신해 준다.

이때, result는 더 작은 값만 넣어준다.

 

선택한 책들로 T를 만들 수 있는지 확인하는 함수는 check 함수이며, alpha 배열에 들어있는 (입력한 문자열) 문자와 책들을 통해 얻은 문자(target) 배열을 비교해 alpha 배열의 값이 더 크다면 (책들을 통해 얻을 수 없는 문자) 단어를 만들 수 없다고 판단한다.

 

 

#include<iostream>
#include<string>
#include<vector>
using namespace std;

int N;
string T;
int alpha[26] = { 0, };
int target[26] = { 0, };
int result = 1600001;
vector<pair<int, string>> arr;

bool check() {
	for (int i = 0; i < 26; i++) {
		if (alpha[i] > target[i]) {
			return false;
		}
	}
	return true;
}
void combination(int counter, int priceSum) {
	if (counter == N) {
		if (check()) result = min(result, priceSum);
		return;
	}
	for (int i = 0; i < arr[counter].second.length(); i++) {
		target[arr[counter].second[i] - 'A']++;
	}
	combination(counter + 1, priceSum + arr[counter].first);
	for (int i = 0; i < arr[counter].second.length(); i++) {
		target[arr[counter].second[i] - 'A']--;
	}
	combination(counter + 1, priceSum);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> T;
	cin >> N;

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

	int C;
	string W;
	
	for (int i = 0; i < N; i++) {
		cin >> C >> W;
		arr.push_back({ C,W });
	}
	
	combination(0, 0);

	if (result == 1600001) cout << -1 << '\n';
	else cout << result << '\n';
	return 0;
}