[플래티넘 5] 백준 1050 - 물약 (파이썬)

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

풀이

여러개의 기초 물약은 가격이 주어지고, 일부 물약은 다른 물약들로 조합하여 만들 있다.

• 조합은 "LOVE=A+2B" 같은 형태로 주어진다.
• 목표: 물약 “LOVE”를 만드는데 필요한 최소 비용 계산하는 것이다.

N, M = map(int, input().split())
stuff = {}

N은 가격이 주어진 물약 수를 나타내며, M은 조합식 수를 나타낸다.

for _ in range(N) :
    name, cost = input().split()
    cost = int(cost)
    stuff[name] = cost

가격이 주어진 물약은 딕셔너리 stuff에 저장한다.

formulas = [input() for _ in range(M)]

LOVE = 2A + 3B 형식으로 전체 조합식을 저장한다.

for i in range(M) :
    result, formula = formulas[i].split("=")
    
    if result not in stuff :
        stuff[result] = -1  # 아직 계산 안 됨
    
    elements = formula.split("+")
    for e in elements :
        k = int(e[0])
        name = e[1:]
        if name not in stuff :
            stuff[name] = -1  # 조합에 필요한 것도 초기화

-1은 아직 비용 계산이 안된 물약을 나타낸다.

while True :
    update = False

    for i in range(M) :
        result, formula = formulas[i].split("=")
        elements = formula.split("+")

        computable = True
        sum = 0
        for e in elements :
            k = int(e[0])
            name = e[1:]

            if stuff[name] == -1 :
                computable = False
                break
            else :
                sum += k * stuff[name]
                sum = min(sum, MAX_VAL)  # 오버플로 방지

        if computable :
            if stuff[result] == -1 or stuff[result] > sum :
                stuff[result] = sum
                update = True

    if not update :
        break

모든 조합식을 순회하면서, 조합 가능한 경우에만 최소 비용을 갱신한다.

갱신이 일어났으면 한 번 더 반복하며, 더이상 갱신이 없으면 종료한다.

코드

# 백준 1050 - 물약
# 분류 : 자료구조

import re

N, M = map(int, input().split())
MAX_VAL = 10000000001

stuff = {}
for _ in range(N) :
    name, cost = input().split()
    cost = int(cost)
    stuff[name] = cost

formulas = [input() for _ in range(M)]

for i in range(M) :
    result, formula = formulas[i].split("=")
    
    if result not in stuff :
        stuff[result] = -1
    
    elements = formula.split("+")
    for e in elements :
        k = int(e[0])
        name = e[1 : ]

        if name not in stuff :
            stuff[name] = -1

while True :
    update = False

    for i in range(M) :
        result, formula = formulas[i].split("=")
        elements = formula.split("+")

        computable = True
        sum = 0
        for e in elements:
			    match = re.match(r"(\\d+)([A-Z]+)", e)
			    k = int(match[1])
			    name = match[2]
			
			    if name not in stuff or stuff[name] == -1:
			        computable = False
			        break
			    else:
			        cost = k * stuff[name]
			        if cost > MAX_VAL:
			            cost = MAX_VAL
			        sum += cost
			        if sum > MAX_VAL:
			            sum = MAX_VAL

        if computable :
            if stuff[result] == -1 or stuff[result] > sum :
                stuff[result] = sum
                update = True

    if not update :
        break

if "LOVE" in stuff and stuff["LOVE"] != -1 :
    print(stuff["LOVE"])
else :
    print(-1)