[Python Algorithm] 연속합 BOJ #1912

문제

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

1912번: 연속합

 

내 문제 풀이

import sys
sys.setrecursionlimit(1000000)

n = int(input())
nums = list(map(int, input().split()))
sums = [nums[0]]

for i in range(1, n):
    if nums[i] < sums[-1] + nums[i]:
        sums.append(sums[-1] + nums[i])
    else:
        sums.append(nums[i])

print(max(sums))

👉 DP 문제로, 연속되는 수들의 합의 최대를 순서대로 누적해주는 것이 포인트 !

• 입력받은 nums 리스트를 순차적으로 돌며 (현재 값 + 누적 합)과 (현재 값)을 비교했다.
• (현재 값)이 더 클 경우 앞에서 연속된 수들의 합을 더하는 것이 손해이므로
  현재 값을 그대로 sum 리스트에 추가했다.
• (현재 값 + 누적 합)이 더 클 경우, 누적해온 합을 더하는 것이 이득이므로
  현재값에 누적한 값을 더한 값을 sums 리스트에 추가했다.
• 위와 같은 실행을 통해 앞의 수에 연속하여 값을 더할 것인지,
  아니면 새로운 연속 합을 만드는 것이 맞는지 판별해 주면 된다.

 

💡 피드백

• 주어진 예시를 분석해보면 쉽게 풀이 방법을 알 수 있는 문제였다.