[LeetCode] 2463. Minimum Total Distance Traveled

https://leetcode.com/problems/minimum-total-distance-traveled/description/?envType=daily-question&envId=2024-10-31

leetcode - Minimum Total Distance Traveled

문제 유형: 다이나믹 프로그래밍, 슬라이딩 윈도우

문제 난이도: Hard

 

문제

There are some robots and factories on the X-axis. You are given an integer array robot where robot[i] is the position of the ith robot. You are also given a 2D integer array factory where factory[j] = [positionj, limitj] indicates that positionj is the position of the jth factory and that the jth factory can repair at most limitj robots.

The positions of each robot are unique. The positions of each factory are also unique. Note that a robot can be in the same position as a factory initially.

All the robots are initially broken; they keep moving in one direction. The direction could be the negative or the positive direction of the X-axis. When a robot reaches a factory that did not reach its limit, the factory repairs the robot, and it stops moving.

 

At any moment, you can set the initial direction of moving for some robot. Your target is to minimize the total distance traveled by all the robots.

 

Return the minimum total distance traveled by all the robots. The test cases are generated such that all the robots can be repaired.

 

Note that

• All robots move at the same speed.
• If two robots move in the same direction, they will never collide.
• If two robots move in opposite directions and they meet at some point, they do not collide. They cross each other.
• If a robot passes by a factory that reached its limits, it crosses it as if it does not exist.
• If the robot moved from a position x to a position y, the distance it moved is |y - x|.

고유한 위치를 가진 로봇들과 고유한 위치의 공장이 x축 위에 있습니다. (로봇들간, 공장들간에서만 고유)

로봇은 한 쪽으로만 이동가능하고, 충돌하지 않고, 모든 로봇의 속도는 똑같습니다.

 

로봇이 공장에 도착하면, 로봇은 수리됩니다.

공장에는 최소 수용량만큼의 로봇을 머물게 할 수 있습니다.

최소한의 로봇들의 이동거리를 구하시오.

단, 반드시 모든 로봇들이 수리받을 수 있도록 보장되며, 로봇은 한 방향으로만 이동가능합니다.

 

풀이

https://leetcode.com/problems/minimum-total-distance-traveled/solutions/5988185/beats-100-working-31-10-2024-explained-step-by-step-happy-halloween-night-shift/?envType=daily-question&envId=2024-10-31

의 풀이로부터 도움받았다..

 

우선, 로봇들과 공장들 배열을 정렬해준다.

dp[i][j]는, i번부터 로봇을 놔야할 때, j번공장부터 갈 수 있는 최소 로봇들의 이동거리의 합을 말한다.

 

때문에, 역추적으로 dp값들을 채워가야 한다.

j번째 공장부터 보면서, i번째 로봇에 대해 고려해본다.

 

처음에는 deque에 {n, 0}을 넣는다. 이는 기본적으로 최대 수용인원을 이미 담아서 못 추가한다는 의미이다.

 

i번로봇을 j번 팩토리에 넣을 때 추가되는 이동거리를 계속 누적한다.

그러고, deque의 맨 앞 요소가 팩토리 j의 수용능력을 넘는동안, deque에서 인덱스를 제거한다.

deque의 마지막 요소의 거리가 새로 계산한 dp[i][j+1] - prefix보다 크다면, 최소값이 아니란 뜻으로, 제거한다.

 

dp[i][j+1] - prefix는, 팩토리 j에 로봇을 배정하기 전의 비용이란 의미이다.

dq에는 {i, dp[i][j+1] - prefix}를 뒤에 넣는다.

dp[i][j]에는 현재 dq의 맨 앞에 있는 비용 + prefix를 저장한다.

즉, 놓기 이전에 값 + 이번 팩토리의 누적값이다.

 

최종적으로, dp[0][0]을 반환한다.

 

아래는 dry-run이다:

 

 

 

코드

C++

class Solution {
public:
    long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
        sort(robot.begin(), robot.end());
        sort(factory.begin(), factory.end());
        int n = robot.size();
        int m = factory.size();

        vector<vector<long long>> dp(n+1, vector<long long>(m+1, LLONG_MAX));

        for(int j = m-1; j >= 0; --j) {
            long long prefix = 0;
            deque<pair<int, long long>> dq;
            dq.push_back({n, 0});
            for(int i = n-1; i >= 0; --i) {
                prefix += abs(robot[i] - factory[j][0]);

                while(!dq.empty() && dq.front().first > i + factory[j][1]) {
                    dq.pop_front();
                }

                while(!dq.empty() && dq.back().second >= dp[i][j+1] - prefix) {
                    dq.pop_back();
                }

                dq.push_back({i, dp[i][j+1] - prefix});
                dp[i][j] = dq.front().second + prefix;
            }   
        }

        return dp[0][0];
    }
};