백준 16508번 전공책 (C++)

문제 링크 : https://www.acmicpc.net/problem/16508

16508번: 전공책

문제 요약

 

1. 민호가 만들고자하는 단어인 문자열 T(1 ≤ |T| ≤ 10)가 주어진다. T는 항상 대문자이다.

2. 민호가 가진 전공책의 개수 N과, N개의 전공책 가격 Ci (10,000 ≤ Ci ≤ 100,000), 전공책 제목을 의미하는 문자열 Wi (1 ≤ |Wi| ≤ 50)가 주어진다. Wi는 항상 대문자이다.

3. 민호가 만들고자 하는 문자열을 만들기 위해 사용해야하는 전공책의 최소한의 가격을 출력하라.

 

 

핵심 포인트

 

조합으로 접근하면 쉽게 풀 수 있습니다.

조합의 시간복잡도는 O(2^n)이고 전공책의 최대 개수는 16이므로, 시간초과는 발생하지 않습니다.

 

 

문제 풀이

 

전체 코드입니다.

#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 987654321
using namespace std;

int goal[26], alphabet[26], cnt, ans = MAX;
vector<pair<int, string>> v;

void input() {
    int price;
    string minho,title;
    cin >> minho;
    for (auto i : minho) goal[i - 'A']++;
    cin >> cnt;
    for (int i = 0; i < cnt; ++i) {
        cin >> price >> title;
        v.push_back({ price,title });
    }
}

bool check() {
    for (int i = 0; i < 26; i++) {
        if (goal[i] > alphabet[i]) return false;
    }
    return true;
}

void comb(int book, int priceSum) {
    if (book >= cnt) {
        if (check()) ans = min(ans, priceSum);
        return;
    }
    string temp = v[book].second;
    for (auto i : temp) alphabet[i - 'A']++;
    comb(book + 1, priceSum + v[book].first);
    for (auto i : temp) alphabet[i - 'A']--;
    comb(book + 1, priceSum);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input(); // 1
    comb(0, 0); // 2
    if (ans == MAX) cout << -1 << "\n"; 
    else cout << ans << "\n";
    return 0;
}

 

 

input()함수에서는 문제에서 주어지는 입력값들을 저장합니다. 포인트는 민호가 원하는 알파벳들의 갯수를 저장하는 것입니다.

 

comb함수는 재귀함수 기반의 조합을 이용해 선택한 책들에 포함된 알파벳의 갯수들을 저장합니다.

만약 현재 책의 번호가 book의 사이즈(전공책의 개수) 이상일 경우, 민호가 원하는 알파벳 갯수들과 현재까지 저장한 알파벳의 갯수와 비교하여 단어를 만들 수 있는지 없는지를 체크합니다. 만들수 있다면 전공책 가격의 최소 가격을 갱신합니다.

 

마지막으로 ans가 MAX라면 원하는 문자열을 만들 수 없다는 뜻으로 -1을 출력합니다.

그렇지 않을 경우 정답을 출력합니다.