문제

문제 이해

DP문제 유형중 카데인 알고리즘 문제이다. Kadane's Algorithm

수열에서 연속된 값을 합이 최댓값을 구하는 문제이다. 연속된 값의 합이란 값을 넘어가는 것없이 붙어있는 값들끼리 더했을때는 최댓값을 말하는 것이다.

dp 점화식?

dp[n] -> n번까지의 dp의 최댓값. 이게 아래에 풀어서 쓴 글을 보면 알기 쉽다.

arr 값의 개수: 10

인덱스 0 1 2 3 4 5 6 7 8 9 10 11
값 >> 0 10 -4 3 1 5 6 -35 12 21 -1

dp 초기값

인덱스 0 1 2 3 4 5 6 7 8 9 10 11
값 >> 0 0 0 0 0 0 0 0 0 0 0 0

i = 1일때
dp[1] = max(dp[0], 0) + arr[1] = max(0, 0) + 10 = 10

i = 2일때
dp[2] = max(dp[1], 0) + arr[2] = max(10, 0) + -4 = 6

i = 3 일때
dp[3] = max(dp[2], 0) + arr[3] = max(6, 0) + 3 = 9

i = 4 일때
dp[4] = max(dp[3], 0) + arr[4] = max(9, 0) + 1 = 10

i = 5일때
dp[5] = max(dp[4], 0) + arr[5] = max(10, 0) + 5 = 15

i = 6일때
dp[6] = max(dp[5], 0) + arr[6] = max(15, 0) + 6 = 21

i = 7일때
dp[7] = max(dp[6], 0) + arr[7] = max(21, 0) + -35 = -14

i = 8일때
*직전dp값이 음수일 때는 max에서 0만 넘어감. 이전까지 연속된 수열은 포함 안한다는 뜻
dp[8] = max(dp[7], 0) + arr[8] = max(-14, 0) + 12 = 12

i = 9일때
dp[9] = max(dp[8], 0) + arr[8] = max(12, 0) + 21 = 33

i = 10일때
dp[10] = max(dp[9], 0) + arr[10] = max(33, 0) + -1 = 32

8번을 보면 중간에 음수가 섞여있어도 합이 크다면 그 값을 채택하는 것을 알 수 있다.

코드

# 백준 1912번 연속합

N = int(input())
arr = [0] + list(map(int, input().split()))

# dp[n]: n까지의 연속된 값의 합의 최댓값
dp = [0 for _ in range(N+1)]

#kadane' algorithm 연속 부분 수열의 최대합 알고리즘
for i in range(1, N+1):
    dp[i] = max(dp[i-1], 0) + arr[i]

# 슬라이싱을 하는 이유는 dp[0]이 쓰는 값이 아니여서서
print(max(dp[1:]))

DP는 대부분 어렵다. 그래서 배낭문제 같은 경우는 잘 못 푼다. 카데인은 이해하기는 그렇게 어렵지 않지만 이게 좀 더 응용되면 어려워질 것 같다. 짧지만 강력한 코드다.