[BOJ/python] 1912: 연속합

문제

✔️ silver 2
다이나믹 프로그래밍

문제 흐름

문제는 다음과 같은 흐름을 따라 진행했다.

1. nums에 input 수열을 입력받아 저장한다.
2. 누적합을 저장할 sum과 각 수까지의 최대 연속합을 저장할 memo를 생성한다.
   초기값으로 memo[0]을 nums[0], sum을 nums[0]이 양수라면 nums[0], 음수라면 0으로 설정한다.
3. i = 1부터 n-1까지 4 ~ 6을 반복한다.
4. sum과 nums[i]를 더한 값을 sum에 저장한다.
5. sum과 memo[i - 1]을 비교해 더 큰 값을 memo[i]에 저장한다.
6. 만약 sum값이 음수로 계산되었다면 0으로 초기화한다.

6.의 경우 sum을 계산하며 한번에 처리해줘도 괜찮을 것 같다.

예제 입력 1에 대해 이해가 쉽게 정리하자면 다음과 같다.

추가적으로 내가 문제를 풀며 참고한 반례들을 첨부한다!

# 반례 1
input:
3
1 1 1
answer: 3

# 반례 2
input:
5
-10 50 100 100 100
answer: 350

코드

# 연속합
# dp

import sys
input = sys.stdin.readline

def dp(nums: list):
    n = len(nums)
    memo = [0 for i in range(n)]
    memo[0] = nums[0]
    sum = max(nums[0], 0)

    for i in range(1, n):
        sum += nums[i]
        memo[i] = max(memo[i - 1], sum)
        if sum < 0:
            sum = 0
    # print(memo)
    return memo[-1]

if __name__ == "__main__":
    n = int(input())
    nums = list(map(int, input().split()))
    result = dp(nums)
    print(result)

마무리

스스로 생각해낸 방식이라 맘에 들었다.
물론 모든 문제는 스스로 풀어야하는게 맞지만 .. ^^
오랜만에 gpt 도움 없이 푼 기분이다.

참고로 나는 sum이 0으로 초기화되는 초건과 sum의 초기값 설정 부분에서 삐끗해서 반례를 많이 찾았다.