[BOJ 1912] 연속합

문제 요약

길이 n인 정수 수열이 주어진다.
연속된 몇 개(최소 1개)를 선택해서 만들 수 있는 부분합 중 최댓값을 출력한다.

내가 푼 흐름

DP 문제를 많이 안 풀어봐서, 처음에는 감이 잘 안 왔다.
GPT에게 “최대 부분 배열(연속합) 같은 DP 문제는 어떻게 접근하는지” 개념 설명을 듣고 나서 구현했다.

핵심 아이디어는:

• i번째 원소를 반드시 포함하는 “최대 연속합”을 dp[i]라고 두면,
• dp[i]는 두 가지 선택지 중 큰 값이다.

1) 이전 연속합에 이어서 더하기: dp[i-1] + nums[i]
2) i에서 새로 시작하기: nums[i]

즉 점화식:

• dp[i] = max(dp[i-1] + nums[i], nums[i])

정답은 dp 중 최댓값.

내 코드

n = int(input())

nums = list(map(int, input().split()))

dp = [nums[0]]

for i in range(1, n):
    dp.append(max(dp[i-1] + nums[i], nums[i]))

print(max(dp))

코드 해설 (DP 관점)

• dp[i]는 “i에서 끝나는 최대 연속합”이다. (i 원소는 반드시 포함)
• dp[i-1] + nums[i]가 더 크면 “이전 구간을 이어가는 것이 유리”
• nums[i]가 더 크면 “이전 구간은 버리고 i부터 새로 시작하는 것이 유리”
• 모든 i에 대해 계산한 뒤, 전체 최댓값이 답이 된다.

이 방식은 흔히 Kadane’s Algorithm(카데인 알고리즘) 으로도 알려져 있다.

이번 문제로 배운 점

• DP는 “상태(state)를 어떻게 정의하느냐”가 핵심이다.
  여기서는 dp[i] = i에서 끝나는 최대 연속합으로 정의하니 점화식이 깔끔해졌다.
• “이전 결과에 이어붙일지 vs 새로 시작할지” 같은 두 선택지 비교가 DP의 전형적인 패턴이다.
• 전체 최댓값을 구하는 문제라도, 중간 상태는 “끝이 i인 최댓값”처럼 로컬하게 정의하면 풀리는 경우가 많다.