[LeetCode] 1266. Minimum Time Visiting All Points

https://leetcode.com/problems/minimum-time-visiting-all-points/description/

Minimum Time Visiting All Points - LeetCode

leetcode - Minimum Time Visiting All Points

문제 유형 : 수학

문제 난이도 : Easy 

 

문제

On a 2D plane, there are n points with integer coordinates points[i] = [x_i, y_i]. Return the minimum time in seconds to visit all the points in the order given by points.

You can move according to these rules:

• In 1 second, you can either:
  • move vertically by one unit,
  • move horizontally by one unit, or
  • move diagonally sqrt(2) units (in other words, move one unit vertically then one unit horizontally in 1 second).
• You have to visit the points in the same order as they appear in the array.
• You are allowed to pass through points that appear later in the order, but these do not count as visits.

 

2차원 공간에 n개의 점이 있다. points배열로 주어지며, points[i] = [x_i, y_i]의 형태로 주어진다.

이 점들을 주어진 배열의 순서대로 탐색할 때의 최소 시간을 반환하시오.

 

1초 동안 당신은 가로, 세로로 한 칸 씩, 또는 대각선으로 sqrt(2)만큼 움직일 수 있습니다.

당신은 순서대로 점을 지나가는 길에 다른 점을 통과할 수 있지만, 그 점을 방문한 것으로 간주하지 않습니다.

 

 

풀이

1초동안 가로, 세로, 대각선으로 1씩 가능하기 때문에, 두 점 사이의 거리는 x축거리와 y축거리의 최대값이 됩니다.

순서대로 각 두 점간의 거리들을 누적시켜주면 총 이동시간을 구할 수 있습니다.

 

 

코드

C++

class Solution {
public:
    int getMinTime(vector<int> &a, vector<int> &b) {
        return max(abs(b[0]-a[0]), abs(b[1]-a[1]));
    }

    int minTimeToVisitAllPoints(vector<vector<int>>& points) {
        const int n = points.size();
        int sum = 0;
        for(int i = 0; i < n-1; i++) {
            sum += getMinTime(points[i], points[i+1]);
        }

        return sum;
    }
};