백준 16508 전공책

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

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

#define INF 987654321

using namespace std;

//문자열 t에 대해 각 알파벳의 개수
vector<int> cnt(26, 0);

//각 책에 대한 값
vector<int> price;


int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string t;
    int n;


    cin >> t;

    for (int i = 0; i < t.size(); i++) {
        cnt[t[i] - 'A']++;
    }

    cin >> n;

    //각 책에 대한 알파벳의 개수
    vector<vector<int>> alpha(n, vector<int>(26, 0));

    for (int i = 0; i < n; i++) {
        int tprice;
        string tbook;

        cin >> tprice >> tbook;

        price.push_back(tprice);
        for (int j = 0; j < tbook.size(); j++) {
            alpha[i][tbook[j]-'A']++;
        }
    }

    int ans = INF;

    for (int b = 1; b < round(pow(2, n)); b++) {

        vector<int> temp = cnt;
        int cost = 0;

        for (int i = 0; i < n; i++) {
            if (b & (int) round(pow(2, i))) {
                for (int j = 0; j < 26; j++) {
                    temp[j] -= alpha[i][j];
                }
                cost += price[i];
            }
        }

        if (*max_element(temp.begin(), temp.end()) <= 0) ans = min(ans, cost);



    }

    if (ans != INF) {
        cout << ans;
    } else {
        cout << -1;
    }


    return 0;
}

 

1. 문제

단어 하나와 n권의 책의 이름, 가격이 주어진다. 책의 이름의 알파벳을 조합하여 단어를 만들려고 할 때, 필요한 책의 최소 비용을 구하는 문제이다.

2. 풀이

브루트포스 문제이다. 어떤 경우의 수를 사용하던 최솟값이 갱신될 수 있는 여지가 있으므로 모든 경우의 수를 탐색해야 한다. 알고리즘 분류에 비트마스킹이 있어 해보았다.

    cin >> t;

    for (int i = 0; i < t.size(); i++) {
        cnt[t[i] - 'A']++;
    }

    cin >> n;

    //각 책에 대한 알파벳의 개수
    vector<vector<int>> alpha(n, vector<int>(26, 0));

    for (int i = 0; i < n; i++) {
        int tprice;
        string tbook;

        cin >> tprice >> tbook;

        price.push_back(tprice);
        for (int j = 0; j < tbook.size(); j++) {
            alpha[i][tbook[j]-'A']++;
        }
    }

 단어를 입력받고, 그 단어의 각 알파벳 수를 배열에 저장한다. 그 후 책의 비용을 price라는 배열에 저장하고, 책의 이름을 입력받아 각 책의 알파벳 수를 alpha라는 배열에 저장한다.

    int ans = INF;

    for (int b = 1; b < round(pow(2, n)); b++) {

        vector<int> temp = cnt;
        int cost = 0;

        for (int i = 0; i < n; i++) {
            if (b & (int) round(pow(2, i))) {
                for (int j = 0; j < 26; j++) {
                    temp[j] -= alpha[i][j];
                }
                cost += price[i];
            }
        }

        if (*max_element(temp.begin(), temp.end()) <= 0) ans = min(ans, cost);



    }

 b는 1부터 2^n-1까지 탐색한다. 2^n을 2진수로 표현하면 100...00(0이 n개)이므로 1 작으면 1이 n개인 2진수까지 사용하므로 n개의 책을 이용하는 모든 경우를 탐색할 수 있다. 

 temp에는 단어의 알파벳 수가 있는 벡터를 담는다. 책을 하나씩 보면서 b&pow(2, i) 즉, 해당 책이 이번 루프에 사용될 경우 temp에서 현재 책의 각 알파벳을 뺀다. 

 만약 해당 책들로 단어를 만들 수 있다면 temp의 모든 값은 0 이하가 된다. 그럴 경우 ans를 갱신한다. 이를 출력하면 정답을 구할 수 있다.