[백준 16508번] 파이썬 - 전공책

백준 16508 - 전공책

시간 제한 1초, 메모리 제한 512MB

# 조건

• 곧 졸업을 앞둔 민호는 대학교 생활 동안 구매만 해놓고 한 번도 펴보지 않은 전공책에 먼지가 쌓여 있는 것을 보고는, 이 책들을 어떻게 처리해야 할지 고민 중이다.
• 열심히 고민한 끝에 민호는 결국 전공책을 모두 버리기로 마음먹었다.
• 하지만 그냥 버리기엔 심심한 민호는 전공책 제목에 있는 글자들을 오려서 단어 만들기 놀이를 하려고 한다.
• 단어 만들기 놀이는 아래 예시와 같다.
  • 1번 책 : COMPUTERARCHITECTURE (35,000원)
  • 2번 책 : ALGORITHM (47,000원)
  • 3번 책 : NETWORK (43,000원)
  • 4번 책 : OPERATINGSYSTEM (40,000원)
• 만약 민호가 만들고 싶은 단어가 ALMIGHTY라고 하면, 위 4개의 책 중, 1번 책에서 A를, 2번 책에서 L, M, I, G, H, T를, 4번 책에서 Y를 오려내어 원하는 단어를 만들 수 있다.
  • 이때 드는 비용은 1번, 2번, 4번 책 가격의 합인 122,000원이다.
• 만약 ANT라는 단어를 만들고 싶다고 하면, 2번 책에서 A를, 3번 책에서 N, T를 오려내어 원하는 단어를 만들 수 있다.
• 이때 드는 비용은 2번과 3번 책 가격을 합하여 90,000원이다. 그런데, ANT라는 단어에서 A를 2번 책에서 오려내지 않고, 4번 책에 있는 A를 오려낼 수도 있다. 만약 4번 책에서 A를 오려냈을 때 드는 비용은 3번과 4번 책 가격을 합하여 83,000원으로 2번과 3번 책을 고른 비용보다 작다.
• 하지만, 4번 책에는 ANT가 모두 포함되어 있으므로, 4번 책만 선택했을 때 드는 비용이 40,000원이다. 이는 ANT라는 단어를 만들기 위해서 가장 적은 비용이다.
• 민호는 여러 개의 전공책들을 나열해 놓고는, 심각한 고민 끝에 전공책 제목에 있는 글자를 오려내어 자신이 원하는 단어를 만들기 위해서는 여러 가지 경우가 있다는 것을 깨달았다.
• 매우 심심했던 민호는 가장 적은 비용으로 자신이 원하는 단어를 만들려면 어떤 전공책들을 선택해야 하는지 궁금했다.
• 하지만 일일이 가능한 조합을 만들어 보는 것은 매우 시간 낭비라고 생각한 민호는 컴퓨터공학과답게 프로그램을 만들려고 한다.
• 민호를 도와 각 전공책의 가격과 제목이 주어졌을 때, 가장 적은 비용으로 민호가 원하는 단어를 만들기 위해서 어떤 전공책을 선택해야 하는지 알아보자.

입력

• 첫 번째 줄에는 민호가 만들고자 하는 단어를 의미하는 문자열 T (1 ≤ |T| ≤ 10)가 주어진다.
• T는 항상 대문자이며, |T|는 문자열 T의 길이를 의미한다.
• 두 번째 줄에는 민호가 가진 전공책의 개수를 의미하는 정수 N (1 ≤ N ≤ 16)이 주어진다.
• 다음 N개의 각 줄에는 전공책 가격을 의미하는 정수 Ci (10,000 ≤ Ci ≤ 100,000)와 제목을 의미하는 문자열 Wi (1 ≤ |Wi| ≤ 50)가 주어진다. _Wi_는 항상 대문자이다.

출력

• 민호가 원하는 단어 T를 만들기 위해서 선택해야 하는 전공책의 가격의 합을 출력한다.
• 만약 단어를 만들 수 없다면 -1을 출력한다.

# 접근 방법

• 브루트 포스로 풀어주었다.
• 우선 입력받는 책의 제목을 Counter 모듈을 이용하여 각 알파벳의 갯수와 책의 가격을 prices 리스트에 담아주었다.
• 주어지는 책들로 만들 수 있는 모든 경우의 수를 탐색해준다.
  • 2^16이므로 충분하다.
  • ex) 1번 1번 1번, 1번 1번 2번과 같은 조합을 의미한다.
• 각 책이 포함된 경우 해당 책의 가격과 포함된 알파벳을 넣어주고 모든 책에 대해 해당 작업이 끝났다면 check 함수를 실행해준다.
• 주어진 target의 모든 알파벳이 해당 조합에 가능하다면 가격을 min으로 구해준다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline
from collections import Counter

def check(string):
    for t in target:
        if t in string and string[t] != 0:
            string[t] -= 1
        else:
            return False
    return True

target = input().strip()
N = int(input())
prices = []
for n in range(N):
    price, title = map(str, input().strip().split())
    prices.append([int(price), Counter(title)])
result = float('inf')

for i in range(1<<N):
    price = 0
    alpha = Counter()
    for j in range(N):
        if (i & 1 << j):
            price += prices[j][0]
            alpha += prices[j][1]

    if check(alpha):
        result = min(result, price)

print(result if not result == float('inf') else -1)