C++로 정원에 물을 주기 위해 열어야 하는 최소 수도꼭지 개수 구하기

x축 위에 1차원 정원이 있다고 가정해 보겠습니다. 정원의 시작 위치는 0이고 끝 위치는 n입니다. 정원에는 [0, 1, ..., n] 위치에 총 n+1개의 수도꼭지가 설치되어 있습니다. 정수 n과 길이가 n+1인 배열 ranges가 주어질 때, ranges[i]는 i번째 수도꼭지를 열었을 때 [i - ranges[i], i + ranges[i]] 구간에 물을 줄 수 있다는 의미입니다.

우리의 목표는 정원 전체에 물을 줄 수 있도록 열어야 하는 수도꼭지의 최소 개수를 구하는 것입니다. 만약 어떤 조합을 사용해도 정원 전체를 커버할 수 없다면 -1을 반환해야 합니다.

예를 들어 n = 5이고 ranges = [3, 4, 1, 1, 1, 0]인 경우 정답은 1입니다. 두 번째 수도꼭지(인덱스 1) 하나만 열어도 [-3, 5] 구간 전체, 즉 정원 전체를 커버할 수 있기 때문입니다.

접근 방법: 그리디 알고리즘

이 문제는 그리디(Greedy) 기법을 활용한 구간 커버(Interval Covering) 문제로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 각 시작 위치에서 도달할 수 있는 가장 먼 끝점을 미리 계산해 배열에 저장합니다.
• 현재 커버할 수 있는 범위 안에서 가장 멀리 도달하는 지점을 반복적으로 확장합니다.
• 범위가 더 이상 확장되지 않으면 정원 전체를 커버할 수 없으므로 -1을 반환합니다.

알고리즘 단계

1. 크기가 (n + 1)인 배열 v를 선언하고 모든 값을 -1로 초기화합니다. v[u]는 시작점이 u인 수도꼭지가 도달할 수 있는 가장 먼 끝점을 의미합니다.
2. i를 0부터 n까지 순회하며 다음을 계산합니다.
   u := max(i - ranges[i], 0) (구간의 시작점)
   e := min(n, i + ranges[i]) (구간의 끝점)
   v[u] := max(v[u], e) (같은 시작점을 가진 구간 중 가장 긴 것만 유지)
3. v[0]이 -1이면 위치 0을 커버하는 수도꼭지가 없다는 뜻이므로 -1을 반환합니다.
4. curr := v[0]으로 현재 커버 범위의 끝을 설정하고, ret := 1로 초기화합니다.
5. curr < n인 동안 다음을 반복합니다.
   - 인덱스 i부터 curr까지 확인하며 도달 가능한 가장 먼 지점 next를 찾습니다.
   - next가 curr과 같다면 더 이상 확장이 불가능하므로 -1을 반환합니다.
   - curr := next로 갱신하고 ret을 1 증가시킵니다.
6. 반복이 종료되면 ret을 반환합니다. 이 값이 곧 열어야 하는 최소 수도꼭지 개수입니다.

이 전략은 "점프 게임 II(Jump Game II)" 문제와 유사한 그리디 접근 방식으로, 각 단계에서 현재 도달 가능한 범위 안에서 최대한 멀리 나아가기 때문에 시간 복잡도 O(n), 공간 복잡도 O(n)으로 문제를 해결할 수 있습니다.

예제 코드 (C++)

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minTaps(int n, vector<int>& ranges) {
      int ret = 1;
      vector<int> v(n + 1, -1);
      for (int i = 0; i <= n; i++) {
         int u = max(i - ranges[i], 0);
         int e = min(n, i + ranges[i]);
         v[u] = max(v[u], e);
      }
      if (v[0] == -1)
      return -1;
      int curr = v[0];
      int i = 0;
      int next = 0;
      while (curr < n) {
         while (i <= curr) {
            next = max(next, v[i]);
            i++;
         }
         if (next == curr)
         return -1;
         curr = next;
         ret++;
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {3,4,1,1,1,0};
   cout << (ob.minTaps(5, v));
}

입력

5, {3,4,1,1,1,0}

출력

1

동작 과정 살펴보기

예제 입력에서 각 수도꼭지가 형성하는 구간은 다음과 같습니다.

• 수도꼭지 0: [-3, 3] → 시작점 0, 끝점 3 → v[0] = 3
• 수도꼭지 1: [-3, 5] → 시작점 0, 끝점 5 → v[0] = 5 (갱신)
• 수도꼭지 2: [1, 3] → v[1] = 3
• 수도꼭지 3: [2, 4] → v[2] = 4
• 수도꼭지 4: [3, 5] → v[3] = 5
• 수도꼭지 5: [5, 5] → v[5] = 5

결과적으로 v = [5, 3, 4, 5, -1, 5]가 됩니다. v[0] = 5이고 n = 5이므로 curr이 이미 정원의 끝에 도달한 상태이며, 추가로 열어야 할 수도꼭지가 없습니다. 따라서 초기값 1을 그대로 반환하여 최종 정답은 1이 됩니다.