1. 문제 소개

2528. Maximize the Minimum Powered City

2. 나의 풀이법

풀지 못했다...

3. 다른 풀이법

접근법은 이분탐색(Binary Search)과 차분 배열(Difference Array), 그리디 전략(Greedy strategy)을 사용한 풀이이다.

1. 이분 탐색(Binary Search):
   목표 전력 val을 정해놓고 “모든 도시 ≥ val”이 가능한지 판별.
   가능하면 val을 키우고, 불가능하면 줄인다.

2. 차분 배열(Difference Array)
   발전소 추가 시 영향을 받는 구간 [i−r, i+r]에 한 번에 +x 적용.
   누적합으로 현재 전력 합산.

3. 그리디(Greedy) 보충
   왼쪽부터 도시를 순회하며 전력이 val보다 작으면, 그 자리에서 부족한 만큼 발전소를 추가.
   오른쪽에 설치해도 왼쪽은 채워지지 않으므로 “즉시 채우기”가 최적.

이러한 방식으로 푼 풀이가 아래의 코드이다.
시간복잡도는 n = len(stations), D = sum(stations) + k일 때, $O(n\,logD)$이다.

class Solution:
    def maxPower(self, stations: List[int], r: int, k: int) -> int:
        n = len(stations)
        cnt = [0] * (n + 1)

        for i in range(n):
            left = max(0, i - r)
            right = min(n, i + r + 1)
            cnt[left] += stations[i]
            cnt[right] -= stations[i]

        def check(val: int) -> bool:
            diff = cnt.copy()
            total = 0
            remaining = k

            for i in range(n):
                total += diff[i]
                if total < val:
                    add = val - total
                    if remaining < add:
                        return False
                    remaining -= add
                    end = min(n, i + 2 * r + 1)
                    diff[end] -= add
                    total += add
            return True

        lo, hi = min(stations), sum(stations) + k
        res = 0
        while lo <= hi:
            mid = (lo + hi) // 2
            if check(mid):
                res = mid
                lo = mid + 1
            else:
                hi = mid - 1
        return res

4. 결론

아직 Hard는 내게 어렵다...