[LeetCode] 3494. Find the Minimum Amount of Time to Brew Potions

https://leetcode.com/problems/find-the-minimum-amount-of-time-to-brew-potions/description/?envType=daily-question&envId=2025-10-09

Leetcode - Find the Minimum Amount of Time to Brew Potions

문제 유형: 다이나믹 프로그래밍

문제 난이도: Medium

 

문제

You are given two integer arrays, skill and mana, of length n and m, respectively.

In a laboratory, n wizards must brew m potions in order. Each potion has a mana capacity mana[j] and must pass through all the wizards sequentially to be brewed properly. The time taken by the ith wizard on the jth potion is timeij = skill[i] * mana[j].

Since the brewing process is delicate, a potion must be passed to the next wizard immediately after the current wizard completes their work. This means the timing must be synchronized so that each wizard begins working on a potion exactly when it arrives. ​

Return the minimum amount of time required for the potions to be brewed properly.

 

두 정수 배열 skill과 mana가 주어진다. 각각의 길이는 n과 m이다.

n명의 마법사는 각각 skill[i]의 기술 등급을 가지고 있고, m개의 포션을 만들어야 한다. 포션은 각 마법사들이 순차적으로 mana[j]만큼의 작업해야 한다.

즉, 각각 skill[i] * mana[j]만큼 든다.

 

포션의 작업 공정에는 빈 틈이 있어서는 안된다. 앞쪽 마법사가 작업을 하고 나서, 바로 다음 마법사가 일할 수 있어야 한다.

포션의 제조 순서도 이대로 되어야 한다.

 

모든 포션을 만드는 데 드는 최소 시간을 구하시오.

 

풀이

i번째 마법사는 이전 포션작업이 끝났다면, 그 다음 포션작업을 할 수 있다.

done[i+1]을 i번째 마법사의 작업종료시간으로 하자.

아래를 각 mana에 대해 순차적으로 적용한다:

1. i번째 마법사의 종료 시간은 max(자신의 이전 포션작업의 끝, 이전 마법사의 현재 포션작업의 끝) + mana[j] * skill[i] 가 된다.  0 ~ n-1의 순서로 적용한다.

2. 그러나, 역전파가 적용될 수 있다. 뒷 사람의 종료시간에 맞춰서, 자신의 작업시작시간을 더 늦춰야 할 수도 있다.

  이전 작업 시간의 종료(done[i]) = 이번 작업 시간의 종료 - 현재 마법사 소요 시간(mana[j] * skill[i])를 적용한다.

 

최종적인 done[n]을 출력하면 된다.

 

코드

C++

static const int __ = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    return 0;
}();

class Solution {
public:
    long long minTime(vector<int>& skill, vector<int>& mana) {
        int n = skill.size(), m = mana.size();

        vector<long long> done(n+1, 0);
        
        for(int j = 0; j < m; ++j) {
            for(int i = 0; i < n; ++i) {
                done[i+1] = max(done[i+1], done[i]) + mana[j] * skill[i];
            }

            for(int i = n-1; i >= 0; --i) {
                done[i] = done[i+1] - 1LL * mana[j] * skill[i];
            }
        } 

        return done[n];
    }
};