[LeetCode] 2742. Painting the Walls

https://leetcode.com/problems/painting-the-walls/description/

Painting the Walls - LeetCode

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

문제 난이도 : Hard

 

문제

You are given two 0-indexed integer arrays, cost and time, of size n representing the costs and the time taken to paint n different walls respectively. There are two painters available:

• A paid painter that paints the ith wall in time[i] units of time and takes cost[i] units of money.
• A free painter that paints any wall in 1 unit of time at a cost of 0. But the free painter can only be used if the paid painter is already occupied.

Return the minimum amount of money required to paint the n walls.

 

cost 배열과 time 배열이 추가됩니다.

각각 n개의 페인트를 하는 비용과 페인트를 하는 시간이 있습니다.

당신은 n개의 칸을 모두 색칠해야 합니다.

 

유료 페인터는 i번째 벽을 time[i]동안 칠합니다. cost[i]만큼의 돈이 듭니다.

무료 페인터는 아무 벽이나 1의 시간동안 0의 비용으로 일합니다. 대신 유료 페인터가 일을 하고 있을 때에만 사용할 수 있습니다.

 

페인트를 칠하는 최소 비용을 구하시오.

 

풀이

2차원 dp배열을 만들어서, dp[현재 보는 유료 페인터][남은 페인트의 개수]에 따른 최소 비용을 저장합니다.

 

아래부터는 재귀적으로 그 페인터를 쓸지 말지 정합니다.

    남은 개수가 0 이하이면, 더 이상 페인터를 쓸 필요가 없으므로 0을 반환시킵니다.

    마지막 n-1번째까지 보고, n번째까지 왔다면, 더 이상 볼 유료 페인터가 없으므로 큰 수(1e9)를 반환합니다.

    만약 dp[i][bank]가 값이 있다면, 그냥 그 값을 반환합니다.

    아니라면, dp[i][bank]를 구합니다. 이번 유료 페인터를 고용할 경우와 고용하지 않을 경우의 경우의 수들 중, 가장 저렴한 비용을 택합        니다.

 

처음에는 시간 대비 비용이 가장 좋은 페인터부터 고용하여 그리디를 이용하여 풀려고 했으나, 점점 조건들이 복잡해지고, 그리디로는 절대 최적해를 구할 수 없다는 것을 알았다.

 

코드

C++

class Solution
{
public:
    int calculate(vector<int> &cost, vector<int> &time, int i, int bank, vector<vector<int>> &dp)
    {
        if (bank <= 0)
        {
            return 0;
        }
        if (i >= cost.size())
        {
            return 1e9;
        }
        if (dp[i][bank] != -1)
        {
            return dp[i][bank];
        }
        else
        {
            int notTake = calculate(cost, time, i + 1, bank, dp);
            int take = cost[i] + calculate(cost, time, i + 1, bank - time[i] - 1, dp);
            return dp[i][bank] = min(notTake, take);
        }
    }

    int paintWalls(vector<int> &cost, vector<int> &time)
    {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);

        vector<vector<int>> dp(cost.size() + 1, vector<int>(time.size() + 1, -1));
        return calculate(cost, time, 0, time.size(), dp);
    }
};