Baekjoon 16508번 전공책

문제

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

걸린 시간

00 : 36 : 19

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    string T;
    cin >> T;
    vector<int> need(26, 0);
    for(char c : T) need[c-'A']++;
    int N;
    cin >> N;
    vector<vector<int>> alphabet(N, vector<int>(26, 0));
    vector<int> C(N);
    string W;
    for(int i = 0; i < N; i++){
        cin >> C[i] >> W;
        for(char c : W) alphabet[i][c-'A']++;
    }
    int ans = INF;
    for(int mask = 1; mask < round(pow(2, N)); mask++){
        vector<int> temp = need;
        int cost = 0;
        for(int i = 0; i < N; i++){
            if(mask & (int)round(pow(2, i))){
                for(int j = 0; j < 26; j++)
                    temp[j] -= alphabet[i][j];
                cost += C[i];
            }
        }
        if(*max_element(all(temp)) <= 0) ans = min(ans, cost);
    }
    if(ans == INF) cout << -1 << "\n";
    else cout << ans << "\n";
    return 0;
}

비트마스킹 기법을 이용해 2¹⁶-1 가지의 경우의 수를 모두 탐색하여 풀이했다.