[BOJ 16508 // C++] 전공책

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 16508번 문제인 전공책이다.
문제는 아래 링크를 확인하자.

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

 

전공책의 개수 \(N\)이 16 이하임을 확인하자. 즉 전공책을 고르는 경우의 수는 \(2^N\), 즉 65536가지로 충분히 적음을 알 수 있다.

 

따라서 각각의 모든 전공책을 고르는 경우의 수를 방문해 (1) 원하는 문자열을 만들 수 있는지 확인하고 (2) 만들 수 있는 경우들의 전공책 가격의 합의 최솟값을 구해 문제를 해결할 수 있다.

 

글쓴이는 고른 책들의 이름에 포함된 각 문자들의 수를 관리해 원하는 문자열의 각 문자의 수와 비교하는 방식으로 (1) 과정을 구현하였다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

string s;
int N;
int C[16]; string ss[16];
int X[128];
int cnt[128], total;
int ans = 1000000007;
void func(int idx) {
	if (idx == N) {
		bool chk = 1;
		for (char c = 'A'; c <= 'Z'; c++) {
			if (cnt[c] < X[c]) {
				chk = 0;
				break;
			}
		}
		if (chk) ans = min(ans, total);
		return;
	}
	func(idx + 1);
	for (auto &l:ss[idx]) cnt[l]++;
	total += C[idx];
	func(idx + 1);
	total -= C[idx];
	for (auto &l:ss[idx]) cnt[l]--;
}

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

	cin >> s;
	for (auto &l:s) X[l]++;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> C[i] >> ss[i];
	}

	func(0);
	if (ans < 1000000007) cout << ans;
	else cout << -1;
}