Python으로 인접한 두 수의 합이 k 이하가 되도록 만드는 최소 연산 횟수 구하기

문제 설명

음수가 아닌 숫자로 이루어진 리스트 nums와 음수가 아닌 값 k가 주어집니다. 우리는 nums에서 하나의 양수를 선택하여 1만큼 감소시키는 연산을 수행할 수 있습니다. 이때 리스트에서 모든 인접한 두 값의 합이 k 이하가 되도록 만들기 위해 필요한 최소 연산 횟수를 구해야 합니다.

만약 답이 매우 큰 값이라면 결과를 10^9 + 7로 나눈 나머지를 반환합니다.

예를 들어, 입력이 nums = [4, 6, 2, 5], k = 6이라면 출력은 5가 됩니다. 리스트를 [3, 3, 1, 4]로 감소시키면 총 5번의 감소 연산이 수행되며, 이때 모든 인접한 쌍의 합이 6 이하가 되기 때문입니다.

해결 방법

이 문제는 그리디(Greedy) 방식으로 해결할 수 있습니다. 왼쪽부터 차례대로 인접한 두 값을 확인하면서, 합이 k를 초과하는 경우 오른쪽 값을 감소시키는 것입니다. 구체적인 단계는 다음과 같습니다.

• m = 10^9 + 7로 설정합니다.
• ans(연산 횟수)를 0으로 초기화합니다.
• i를 0부터 nums의 길이 - 2까지 반복합니다.
  • sm := nums[i] + nums[i + 1] (인접한 두 값의 합)
  • diff := max(sm - k, 0) (초과분 계산)
  • nums[i + 1] := nums[i + 1] - diff (오른쪽 값을 감소)
  • 만약 nums[i + 1] < 0이면 nums[i + 1] := 0으로 설정합니다.
  • ans := ans + diff (연산 횟수 누적)
• 최종적으로 ans mod m을 반환합니다.

왼쪽 요소는 이미 앞 단계에서 조건을 만족하도록 처리되었기 때문에, 초과분만큼 오른쪽 요소를 줄이는 것이 최소 연산 횟수를 보장하는 전략입니다.

구현 예제

m = 10 ** 9 + 7

class Solution:
    def solve(self, nums, k):
        ans = 0
        for i in range(0, len(nums) - 1):
            sm = nums[i] + nums[i + 1]
            diff = max(sm - k, 0)
            nums[i + 1] -= diff
            if nums[i + 1] < 0:
                nums[i + 1] = 0
            ans += diff
        return ans % m

ob = Solution()
nums = [4, 6, 2, 5]
k = 6
print(ob.solve(nums, k))

입력

[4, 6, 2, 5], 6

출력

5

복잡도 분석

이 알고리즘은 리스트를 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 공간 없이 기존 리스트를 수정하므로 공간 복잡도는 O(1)입니다. 따라서 매우 효율적으로 문제를 해결할 수 있습니다.