[백준 1912][DP][파이썬] 연속합 (feat. 카데인(Kadane) 알고리즘)

문제

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

 

풀이

해당 문제는 최적해가 Subproblem들의 최적해로부터 효율적으로 구해질 수 있다. 즉, Optimal Structure 를 가진다고 말할 수 있다.

 

카데인 알고리즘 (Kadane Algorithm)

본 문제는 Kadane's Algorithm 점화식에 대하여 알고 있지 않다면 통과하지 못한다.

Kadane's Algorithm은 n번째 인덱스까지의 최대 부분합은 배열의 n 번째 값과 n−1 번째 인덱스까지의 부분합에 배열의 n 번째 값을 더한 값 중 큰 값이 부분 수열합중 최댓값이다.

Kadane's Algorithm
D[i]를 i 번째 원소인 부분 수열합 중 최댓값 정의하자.
sequence(수열) = [a_1, a_2, ··· , a_n] 으로 주어졌을 때 i 번째 부분 수열합은 다음과 같다.

D[ 1 ]  =  a_1
D[ i ] = max(a_i , D[i-1] + a_i) (when 1< i <=N)

 

카데인 알고리즘(Kadane Algorithm) 원리 설명 및 증명 영상

https://www.youtube.com/watch?v=4csAswCkXZM&ab_channel=QuanticDev

 

정답 코드

import sys
input=sys.stdin.readline

# 수열 항 개수
N=int(input())

# Boundary Condition
seq=list(map(int,input().split()))
seq.insert(0,0)

D=[0 for _ in range(N+1)]
D[1]=seq[1]

# Kadane's Algorithm
for i in range(2,N+1):
    D[i]=max(D[i-1]+seq[i], seq[i])

#답 출력
print(max(D[1::]))

 

---

시간 초과 답안

처음에 모든 경우의 수를 구하지 않은 풀이법이 떠올라 코드 작성하여 제출하였으나 시간초과로 풀이하지 못하였다. k= 1 ~ N 까지 사각형을 움직여 답을 도출해내는 방법이며, 결국 N이 매우 커지게 되면 시간 복잡도가 O(N^2)로 수렴하기에 시간초과로 통과하지 못하였다.

 

코드

import sys

input=sys.stdin.readline

N=int(input())
answer=[0]

input_list=list(map(int, input().split()))
input_list.insert(0,0)

for k in range(1,N+1):

    tmp_L=[]

    for i in range(1,N+1):
        if i+k > N+1: break

        tmp=0

        for j in range(i,i+k):
            tmp+=input_list[j]

        tmp_L.append(tmp)
    
    answer.append(max(tmp_L))

# 답 도출
print(max(answer[1::])) # 연속 부분합 최댓값이 음수일 경우 고려