2742. Painting the Walls

못풀었던 문제.

cost가 적은 wall 순으로 정렬하여 시간의 합이 나머지 array의 길이와 같거나 커질때 까지 cost를 더하는 방식으로 구하였으나 실패.
상황에 따라서는 cost가 높지만 time도 높아서 하나라도 덜 paid painter를 사용하는 경우가 유리할 수 있기 때문인 것으로 보인다.
DP에서 어려운 부분은 어떤 것을 memoization 할지 알아내는 부분인 것 같다.

처음 index부터 끝까지 탐색해나가며 최소의 cost를 찾는다.

현재 index를 선택할 경우 cost는 다음 두 값의 합이다.

현재 index의 cost cost[i]
다음 index i + 1를 탐색하여 결정된 cost (단, 이미 칠해진 벽의 숫자는 painted + 1 + time[i]로 정해진다)

1은 현재 선택된 벽에 해당되는 숫자
time[i]은 현재 선택된 벽을 칠하는 시간으로 해당 시간 동안 free painter가 추가로 벽을 칠할 수 있다

현재 index를 선택하지 않는 경우 cost는 다음 값이 된다.

다음 index i + 1를 탐색하여 결정된 cost (단, 이미 칠해진 벽의 숫자는 painted로 정해진다)

현재 벽을 paid painter가 칠하지 않기로 했으므로 칠해진 벽의 숫자 painted는 변함이 없다.


class Solution {
public:
    int paintWalls(
        vector<int>& cost, vector<int>& time, 
        vector<vector<int>>& dp,
        int i, int painted) {
        if (painted >= cost.size()) return 0;
        if (i >= cost.size()) return 1e9;
        if (dp[i][painted] != -1) return dp[i][painted];
        int choose = cost[i] + 
            paintWalls(cost, time, dp, i + 1, painted + 1 + time[i]);
        int notChoose = paintWalls(cost, time, dp, i + 1, painted);
        return dp[i][painted] = min(choose, notChoose);
    }

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