leetcode 1326 - Minimum Number of Taps to Open to Water a Garden

https://leetcode.com/problems/minimum-number-of-taps-to-open-to-water-a-garden/

풀이

0부터 n까지 모든 점을 커버하는 최소한의 tab을 고르는 문제이다.

 

모든 점을 커버해야 하므로 0도 커버해야 하는데, 0을 커버하는 많은 tab 중에서는 가장 오른쪽 점까지 커버하는 tab을 고르는 것이 최선이다. 이렇게 고른 tab이 커버하는 가장 오른쪽 점을 r이라고 하자. 이다음 최선의 tab을 고르는 방법도 마찬가지이다. [0, r] 범위에 겹치는 범위를 가지는 다음 tab 중에 가장 오른쪽 점을 커버하는 tab을 고르면 된다. 그리디한 방법으로 tab을 고르는 게 항상 더 좋기 때문이다.

 

어차피 모든 점을 커버해야 하기 때문에 0부터 n 순서대로 확인을 하고, 커버 가능한 가장 오른쪽 점을 갱신하면  O(n)만에 최소한의 tab을 구할 수 있다.

 

 

코드

class Solution {
public:
    int minTaps(int n, vector<int>& ranges) {
        vector<int> cover(n+1);
        for(int i = 0; i <= n; i++) {
            int l = max(0, i - ranges[i]);
            int r = min(n, i + ranges[i]);
            cover[l] = r;
        }
        
        int current = 0, maxR = 0, ans = 0;
        for(int i = 0; i <= n; i++) {
            if(maxR < i) return -1;
            if(current < i) {
                current = maxR;
                ans++;
            }
            maxR = max(maxR, cover[i]);
        }
        
        return ans;
    }
};