[동적계획법/DP] 백준 1912 연속합 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1912번: 연속합

 

 

 

2. 문제 풀이

 연속된 수들의 합 중 가장 큰 값을 출력하는 문제입니다.

 

2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

[Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

 DP문제로, 이전 값과 더한 걸 비교해서 더 큰 걸로 갱신합니다.

 

sum[i] = max(sum[i], sum[i-1]+sum[i])

 단순히 음수를 만나기 전까지만 더하면 답을 찾지 못합니다. 음수를 만나더라도 그 다음에 큰 수가 있으면, 해당 연속합이 더 크기 때문입니다.

 위 점화식대로 갱신하면, 연속합이 i번째 수보다 작을 때까지 구합니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

#입력
N = int(input())
cost = list(map(int, input().split()))

#DP
for i in range(1, N):
    # i번째 수보다 연속합이 크면 갱신
    cost[i] = max(cost[i], cost[i-1]+cost[i])
print(max(cost))