찬우의 이것저것 Chanwoo's blog

[boj 16508 python]전공책

2020-03-27

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

책제목들을 합쳐서 만들수있는 모든 조합을 만들어서 문자열을 만든 후

그 문자열 안에 검색어가 있는지 한글자씩 비교했다.

조합을 만들때 비트연산을 통해서 할 수 있다는 방법이 신기했다.

l = ["A", "B", "C"]
r = []
for i in range(1, 1 << len(l)):
    tmp = ""
    for j in range(len(l)):
        # print(i, j,"/",i&1, i & 1 << j)
        if (i & 1 << j) != 0:
            tmp += l[j]
    r.append(tmp)
print(r) # ['A', 'B', 'AB', 'C', 'AC', 'BC', 'ABC']

이런식으로 책 제목으로 만들 수 있는 모든 문자열을 만들고 원하는 문자가 있는지 한개씩 검사한다.

조합하여 만든 문자열로 해당 단어를 만들수 있는지 검사하는 함수 wordinbook(word, book, price):에 넣어

가능한 경우의 금액을 모두 구하고 그중 가장 작은 금액을 출력한다

import sys

### 문제 제출용 input 
# in_str = input()
# bcnt = int(input())
# price = []
# in_major = []
# for i in range(bcnt):
#     p, m = input().split()
#     price.append(int(p))
#     in_major.append(m)

in_str = "ALMIGHTY"
in_major = ["COMPUTERARCHITECTURE", "ALGORITHM", "NETWORK", "OPERATINGSYSTEM"]
price =[35000,47000,43000,40000]

# print(in_str, bcnt, price, in_major)

def wordinbook(word, book, price):
    cnt = 0
    for w in word:
        if w in book:
            cnt += 1
            book = book.replace(w, ' ', 1) # 오려낸 글자는 없애준다
            # print(book, word)
            if cnt == len(word):
                return price
    return sys.maxsize

result = []

for i in range(1 << len(in_major)):
    search_str = ""
    sum_price = 0
    for j in range(len(in_major)):
        # print(i, j,"/",i&1, i & 1 << j)
        if (i & 1 << j) != 0: # 
            # print(in_major[j])
            search_str += in_major[j]
            sum_price += price[j]
    # print(search_str)

    result.append(wordinbook(in_str, search_str, sum_price))

result = min(result)
if result == sys.maxsize:
    result = -1

print(result)

Related Posts