[백준/python] 16508번 전공책

1. 문제

 

이 문제는 각 단어별 가격이 있고 단어를 조합해서 목표 단어를 만들되, 가격을 최소로 하는 문제이다.

2. 풀이

<아이디어>
알파벳의 개수와 같은 길이의 배열을 만들어 그 원소를 하나씩 비교한다.

1. word 배열 -> t에 주어진 단어에 들어가는 알파벳 개수 표시
2. arr 배열 -> 전공책 각각 주어진 단어에 들어가는 알파벳 개수 표시
3. 금액은 inf로 초기화하고 x 배열을 넣어서 word_making 함수 실행
4-1. x 배열의 어떤 원소가 word 배열의 원소보다 작은 경우
    -> 단어를 만들 수 없으므로 result를 False로 바꾸고 반복문 탈출
4-2. x 배열의 모든 원소가 word 배열의 원소보다 큰 경우
    -> 단어를 만들 수 있다는 뜻 -> price 갱신 후 return
5. 4-1 이후, 전공책을 한 권 씩 포함하면서 x 배열과 가격을 갱신하고 word_making 재귀함수 실행
6. 함수가 종료되고 price가 inf일 경우 -1을, 아닐 경우는 price를 출력

3. 코드

import sys
input = sys.stdin.readline

def word_making(x, p, a):
    global price
    result = True
    for i in range(26):
        if x[i] < word[i]:
            result = False
            break
    if result:
        price = min(price, p)
        return
    for i in range(a, n):
            new_x = [x[j] + arr[i][j] for j in range(26)] 
            word_making(new_x, p + int(books[i][0]), i+1)

t = input().rstrip()
n = int(input())
books = sorted([input().split() for _ in range(n)])

alpha = [chr(i) for i in range(65, 91)]
word = [0] * 26

for i in t:
    idx = alpha.index(i)
    word[idx] += 1

arr = []
for book in books:
    row = [0] * 26
    for i in book[1]:
        idx = alpha.index(i)
        row[idx] += 1
    arr.append(row)

price = float("inf")
x = [0] * 26
word_making(x, 0, 0)

if price == float("inf"):
    print(-1)
else:
    print(price)

4. 결과

<새로 알게 된 사실>

파이썬에서 배열의 덧셈은 각 배열의 원소를 합한 것과 같다.

내가 의도한 것은 두 배열 원소 개수가 같을 때 같은 인덱스끼리 더하는 거였는데

이 부분이 의도대로 되지 않아 처음에 애를 먹었다.

 

<처음에 시간 초과가 난 이유>

visited 배열을 만들어서 했었는데, 굳이 필요가 없음을 알게 되었다.

이 배열을 지우고 코드를 살짝 수정했더니 시간 내로 통과되었다.