[백준 2024/10/13] 1912번 연속합

1. 문제

https://www.acmicpc.net/problem/1912

 

2. 접근 방법

dp 리스트를 만든 후, 해당 idx에서는 해당 idx에서 가장 큰 연속된 수를 포함하도록 코드를 작성하고자 하였다.

 

1. 양수를 만나면, 무조건 포함하는 것이 이득이 된다.
2. 음수를 만나면 더해보고, 0보다 작아진다면 연속된 합을 취소하고 다음 수 부터는 이전 dp[i-1]이 아닌 새로 값을 더하기를 시작하는 것이 좋음.

작성한 코드를 하나씩 보면서 더 알아보자.

 

    for i in range(1, n+1, 1):
        if dp[i-1] < 0:
            dp[i] = nums[i]
            continue
        dp[i] = dp[i-1] + nums[i]

만약 연속된 수들의 합이 0보다 작다면, 새로 dp[i] = nums[i]로 시작한다.

그 외, 크다면 포함해서 더하는 것이 이득이므로, dp[i] = dp[i-1] + nums[i] 를 적어둔다.

 

3. 코드

def get_max_count(nums, n):
    dp = [0] * (n+1)

    for i in range(1, n+1, 1):
        if dp[i-1] < 0:
            dp[i] = nums[i]
            continue
        dp[i] = dp[i-1] + nums[i]

    return max(dp[1:])


if __name__ == "__main__":
    n = int(input())
    nums = list(map(int, input().split()))
    nums.insert(0, 0)
    print(get_max_count(nums, n))