[백준] 16508 전공책

문제

• 전공책 제목에서 알파벳을 오려내서 원하는 단어를 만드려고 한다. 이때 비용은 사용한 전공책의 가격의 합이다.
  • 1 <= |문자열의 길이| <= 10
  • 1 <= 전공책의 개수 <= 16
  • 1 <= |전공책 제목의 길이| <= 50
• 만약 단어를 만들 수 없다면 -1 출력하기

 

풀이 1

• 그리디하게 풀 수 없다!
  • 35000원 짜리 1개, 40000원 짜리 1개 보다는 40000원 짜리 책에서 2개 알파벳 뽑아야 최소비용이니까!
• 완전탐색 문제 (모든 경우의 수 확인하기)
  • 각 전공책을 포함한다 / 안한다 2개의 경우로 생각해 전체 경우를 확인한다.
  • 시간복잡도 : $2^{16}$ 이므로 충분히 계산 가능하다.
• 카운터와 비트마스크를 이용해 각 경우의 수 마다 문자열을 만들 수 있는지 체크하고, 가능하다면 최솟값 갱신
  • 1. 문자열 T에 대한 알파벳 개수 abc_list에 저장하고,
  • 2. 각 경우의 수마다 전공 책에 있는 알파벳을 abc_list 에서 뺀다. (카운터는 - 연산 가능!)
  • 3. abc_list 가 비었다면, 문자열 T를 만들 수 있다는 의미이므로 최솟값을 갱신한다.
• 91% 에서 시간 초과..!!

from collections import Counter
import sys
from copy import deepcopy

T = input()
N = int(input())
books = []              # 책 리스트 (가격, 책제목의 알파벳 개수)
for _ in range(N):
    price, title = input().split()
    books.append((int(price), Counter(title)))

abc_list = Counter(T)   # 문자열 T에서 각 알파벳의 개수
answer = sys.maxsize

# 00..0 ~ 11...1 까지 각 전공책이 포함 되고 포함되지 않는 경우의 수 확인
for i in range(1 << N):
    price = 0
    alphabets = deepcopy(abc_list)  # 문자열 만드는데 필요한 알파벳 개수

    for j in range(N):
        if (i & 1 << j) != 0 :          # j 번째 전공책이 포함된 경우
            price += books[j][0]        # 가격 더하고
            alphabets -= books[j][1]    # 알파벳 개수 제외
    
    if not alphabets :  # 문자열을 만들 수 있다면 최솟값 저장
        answer = min(answer, price)

print(-1) if answer == sys.maxsize else print(answer)

 

풀이 2

• deepcopy 때문이라고 생각해서 deepcopy 없이 확인하는 함수를 만들었다.

 

from collections import Counter
import sys

#  문자열을 만들 수 있는지 확인하기
def check(alphabets, string):
    for w in string :
        # 없는 알파벳이거나, 더이상 추가할 수 없다면 실패
        if w not in alphabets or alphabets[w] == 0 :
            return False
        else:
            alphabets[w] -= 1   # 알파벳 숫자 줄이기
    return True
            
T = input()
N = int(input())
books = []              # 책 리스트 (가격, 책제목의 알파벳 개수)
for _ in range(N):
    price, title = input().split()
    books.append((int(price), Counter(title)))

answer = sys.maxsize

# 00..0 ~ 11...1 까지 각 전공책이 포함 되고 포함되지 않는 경우의 수 확인
for i in range(1 << N):
    price = 0
    alphabets = Counter()      # 전공책의 알파벳들

    for j in range(N):
        if (i & 1 << j) != 0 :          # j 번째 전공책이 포함된 경우
            price += books[j][0]        # 가격 더하고
            alphabets += books[j][1]    # 문자열 더하기
    
    if check(alphabets, T) :  # 문자열을 만들 수 있다면 최솟값 저장
        answer = min(answer, price)

print(-1) if answer == sys.maxsize else print(answer)

 

 

References

• 백준 16508
• 2023.04.28 오늘의 문제