최첨단 자동화 공장은 여러 단계의 공정을 거쳐 물품을 생산합니다. 공장에는 유일한 원재료인 기초 자원(base)이 있으며, 공장 가동 시각 t=1부터 1초에 1개씩 창고에 공급됩니다. (즉, k번째 기초 자원은 시각 t=k에 사용 가능합니다.)
공정은 레시피(process)에 따라 진행되며, 각 레시피는 여러 종류의 입력 자원을 정해진 수량만큼 소비하여 하나의 출력 자원을 생산합니다. 모든 공정은 1초가 소요됩니다.
생산 시작: 레시피에 필요한 모든 입력 자원이 준비되는 즉시 생산을 시작할 수 있습니다. 필요한 자원이 여러 개일 경우, 가장 늦게 준비된 자원의 시간에 맞춰 생산이 시작됩니다.
생산 완료: (생산 시작 시각) + 1초에 결과물이 창고에 입고되며, 그 시각부터 다음 공정의 입력으로 바로 사용할 수 있습니다.
공장의 기계는 수에 제한이 없어 모든 공정은 병렬로 동시에 진행될 수 있습니다.
또한, 자원을 만드는 과정이 서로 맞물려 무한히 반복되는 경우는 없습니다. (예: 'A'를 만들기 위해 'B'가 필요한데, 다시 'B'를 만들기 위해 'A'가 필요한 상황은 발생하지 않습니다.)
기초 자원 base, 레시피 정보 process, 최종 목표 자원 target, 그리고 목표 수량 target_qty가 주어질 때, 목표 수량의 마지막 물품이 창고에 입고되는 최소 시각을 반환하는 solution 함수를 작성해 주세요.
base: 기초 자원의 이름
process: 각 공정의 레시피 정보
각 레시피는 [입력자원1, 수량1, 입력자원2, 수량2, ..., 출력자원, 수량] 형식의 리스트입니다.
target: 최종 목표 자원의 이름
target_qty: 최종 목표 자원의 생산 수량
자원의 이름은 영문 소문자로만 구성됩니다.
자원/레시피의 종류는 100개 이하입니다.
모든 수량(target_qty 포함)은 1 이상 100 이하의 정수입니다.
각 출력 자원은 단 하나의 레시피로만 생산됩니다.
자원을 만드는 과정이 서로 맞물려 무한히 반복되는 경우는 없습니다. (예: 'A'를 만들기 위해 'B'가 필요한데, 다시 'B'를 만들기 위해 'A'가 필요한 상황은 발생하지 않습니다.)
base는 어떤 레시피의 출력으로 등장하지 않습니다.
만약 target이 base와 같은 경우는 없습니다.
target을 만들지 못하는 경우는 없습니다.
예시 1
입력:
base: "a"
process: [["a", 1, "b", 1], ["a", 1, "c", 1], ["b", 1, "c", 1, "d", 1], ["d", 1, "a", 1, "e", 1]]
target: "e"
target_qty: 2
출력: 7
설명: 두 번째 e를 만들기 위한 재료 중 가장 늦게 준비되는 것은 두 번째 d입니다.
두 번째 d를 만들기 위해서는 두 번째 b와 두 번째 c가 필요합니다.
두 번째 b는 4초에 공급되는 4번째 a로 만들어져 5초에 완성됩니다.
두 번째 c는 5초에 공급되는 5번째 a로 만들어져 6초에 완성됩니다.
따라서 두 번째 d는 max(5, 6) = 6초에 생산을 시작하여 7초에 완성됩니다.
두 번째 e는 이 d(7초)와 6번째 a(6초)를 사용하므로, max(7, 6) = 7초에 생산을 시작하여 8초에 완성될 것 같지만, 병렬 생산을 최적화하면 7초에 완성됩니다. (상세 풀이는 해설 참고)
예시 2
입력:
base: "a"
process: [["a", 2, "b", 1], ["a", 1, "c", 2], ["b", 1, "c", 1, "d", 1], ["d", 1, "a", 1, "e", 1]]
target: "e"
target_qty: 2
출력: 8
설명:e 2개를 만들기 위해 총 7개의 a가 필요합니다.
두 번째 b는 4번째 a(4초)를 기반으로 5초에 완성됩니다.
두 번째 c는 5번째 a(5초)를 기반으로 6초에 완성됩니다.
두 번째 d는 b(5초)와 c(6초)를 사용해 7초에 완성됩니다.
두 번째 e는 d(7초)와 7번째 a(7초)를 사용해 max(7, 7) = 7초에 생산을 시작, 최종적으로 8초에 완성됩니다.
예시 3
입력:
base: "wood"
process: [["wood", 1, "gear", 1], ["wood", 1, "rod", 1], ["gear", 2, "rod", 1, "engine", 1]]
target: "engine"
target_qty: 2
출력: 8
설명:engine 2개를 만들기 위해 총 6개의 wood가 필요합니다.
engine 생산에는 gear와 rod가 필요합니다.
두 번째 engine에 필요한 네 번째 gear는 4번째 wood(4초)를 사용해 5초에 완성됩니다.
두 번째 engine에 필요한 두 번째 rod는 6번째 wood(6초)를 사용해 7초에 완성됩니다.
따라서 두 번째 engine은 gear(5초)와 rod(7초) 중 더 늦은 7초에 생산을 시작하여, 최종적으로 8초에 완성됩니다.
a
[["a",1,"b",1],["a",1,"c",1],["b",1,"c",1,"d",1],["d",1,"a",1,"e",1]]
e
2
최첨단 자동화 공장은 여러 단계의 공정을 거쳐 물품을 생산합니다. 공장에는 유일한 원재료인 기초 자원(base)이 있으며, 공장 가동 시각 t=1부터 1초에 1개씩 창고에 공급됩니다. (즉, k번째 기초 자원은 시각 t=k에 사용 가능합니다.)
공정은 레시피(process)에 따라 진행되며, 각 레시피는 여러 종류의 입력 자원을 정해진 수량만큼 소비하여 하나의 출력 자원을 생산합니다. 모든 공정은 1초가 소요됩니다.
생산 시작: 레시피에 필요한 모든 입력 자원이 준비되는 즉시 생산을 시작할 수 있습니다. 필요한 자원이 여러 개일 경우, 가장 늦게 준비된 자원의 시간에 맞춰 생산이 시작됩니다.
생산 완료: (생산 시작 시각) + 1초에 결과물이 창고에 입고되며, 그 시각부터 다음 공정의 입력으로 바로 사용할 수 있습니다.
공장의 기계는 수에 제한이 없어 모든 공정은 병렬로 동시에 진행될 수 있습니다.
또한, 자원을 만드는 과정이 서로 맞물려 무한히 반복되는 경우는 없습니다. (예: 'A'를 만들기 위해 'B'가 필요한데, 다시 'B'를 만들기 위해 'A'가 필요한 상황은 발생하지 않습니다.)
기초 자원 base, 레시피 정보 process, 최종 목표 자원 target, 그리고 목표 수량 target_qty가 주어질 때, 목표 수량의 마지막 물품이 창고에 입고되는 최소 시각을 반환하는 solution 함수를 작성해 주세요.
base: 기초 자원의 이름
process: 각 공정의 레시피 정보
각 레시피는 [입력자원1, 수량1, 입력자원2, 수량2, ..., 출력자원, 수량] 형식의 리스트입니다.
target: 최종 목표 자원의 이름
target_qty: 최종 목표 자원의 생산 수량
자원의 이름은 영문 소문자로만 구성됩니다.
자원/레시피의 종류는 100개 이하입니다.
모든 수량(target_qty 포함)은 1 이상 100 이하의 정수입니다.
각 출력 자원은 단 하나의 레시피로만 생산됩니다.
자원을 만드는 과정이 서로 맞물려 무한히 반복되는 경우는 없습니다. (예: 'A'를 만들기 위해 'B'가 필요한데, 다시 'B'를 만들기 위해 'A'가 필요한 상황은 발생하지 않습니다.)
base는 어떤 레시피의 출력으로 등장하지 않습니다.
만약 target이 base와 같은 경우는 없습니다.
target을 만들지 못하는 경우는 없습니다.
예시 1
입력:
base: "a"
process: [["a", 1, "b", 1], ["a", 1, "c", 1], ["b", 1, "c", 1, "d", 1], ["d", 1, "a", 1, "e", 1]]
target: "e"
target_qty: 2
출력: 7
설명: 두 번째 e를 만들기 위한 재료 중 가장 늦게 준비되는 것은 두 번째 d입니다.
두 번째 d를 만들기 위해서는 두 번째 b와 두 번째 c가 필요합니다.
두 번째 b는 4초에 공급되는 4번째 a로 만들어져 5초에 완성됩니다.
두 번째 c는 5초에 공급되는 5번째 a로 만들어져 6초에 완성됩니다.
따라서 두 번째 d는 max(5, 6) = 6초에 생산을 시작하여 7초에 완성됩니다.
두 번째 e는 이 d(7초)와 6번째 a(6초)를 사용하므로, max(7, 6) = 7초에 생산을 시작하여 8초에 완성될 것 같지만, 병렬 생산을 최적화하면 7초에 완성됩니다. (상세 풀이는 해설 참고)
예시 2
입력:
base: "a"
process: [["a", 2, "b", 1], ["a", 1, "c", 2], ["b", 1, "c", 1, "d", 1], ["d", 1, "a", 1, "e", 1]]
target: "e"
target_qty: 2
출력: 8
설명:e 2개를 만들기 위해 총 7개의 a가 필요합니다.
두 번째 b는 4번째 a(4초)를 기반으로 5초에 완성됩니다.
두 번째 c는 5번째 a(5초)를 기반으로 6초에 완성됩니다.
두 번째 d는 b(5초)와 c(6초)를 사용해 7초에 완성됩니다.
두 번째 e는 d(7초)와 7번째 a(7초)를 사용해 max(7, 7) = 7초에 생산을 시작, 최종적으로 8초에 완성됩니다.
예시 3
입력:
base: "wood"
process: [["wood", 1, "gear", 1], ["wood", 1, "rod", 1], ["gear", 2, "rod", 1, "engine", 1]]
target: "engine"
target_qty: 2
출력: 8
설명:engine 2개를 만들기 위해 총 6개의 wood가 필요합니다.
engine 생산에는 gear와 rod가 필요합니다.
두 번째 engine에 필요한 네 번째 gear는 4번째 wood(4초)를 사용해 5초에 완성됩니다.
두 번째 engine에 필요한 두 번째 rod는 6번째 wood(6초)를 사용해 7초에 완성됩니다.
따라서 두 번째 engine은 gear(5초)와 rod(7초) 중 더 늦은 7초에 생산을 시작하여, 최종적으로 8초에 완성됩니다.
a
[["a",1,"b",1],["a",1,"c",1],["b",1,"c",1,"d",1],["d",1,"a",1,"e",1]]
e
2