LeetCode 풀기 - 1413. Minimum Value to Get Positive Step by Step Sum

1413. Minimum Value to Get Positive Step by Step Sum

문제)

솔루션1)

class Solution:
    def minStartValue(self, nums: List[int]) -> int:
        if nums[0] > 0:
            start = 1
        else:
            start = abs(nums[0]) + 1
        
        while True:
            r = start            
            for n in nums:
                if r+n <= 0:
                    break
                r += n
                
            else:
                return start
            start += 1

솔루션2)

계속 누적해서 더한 경우의 가장 작은 값이 나올텐데, 이 값을 1 이상으로 만들어주는 값을 찾으면 된다.

아래 테이블과 값이 초기 값을 0 으로 주고 계속 더해 나갔을 때 가장 최소값은 -4이다. 

그렇다면 5 이상의 값을 초기값을 설정해서 계산하게되면 최소값을 1이 되기 때문에 값이 5가 되는 것이다.

idx	nums[i]	sum	최소값
0	-3	0 (초기값) - 3   = -3	-3
1	2	-3 + 2 = -1	-4
2	-3	-1 - 3  = -4	-4
3	4	-4 + 4 = 0	-4
4	2	0 + 2  = 2	-4

 

class Solution:
    def minStartValue(self, nums: List[int]) -> int:
        return abs(min(accumulate(nums, initial=0))) + 1