[백준] 1912 파이썬(python) : 연속합

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

1912번: 연속합

 

 

예제 1)

10	-4	3	1	5	6	-35	12	21	-1
10	6	9	10	15	21	-14	12	33	32

 

연속된 몇개의 수를 더해서 최대값을 출력하는것이 문제의 요구사항이니까 현재위치에서 음수가 나왔을때 이전 인덱스까지의 dp와 더할때 0 밑으로 내려가 음수가 되는지 확인해야 한다. 더한 값이 음수가 된다면 연속된 합을 유지할 수 없다. 하지만 더했을때 음수가 아니고 그 다음 위치의 값을 더해줌으로써 이전항보다 커진다면 연속합을 유지할 수 있다.

 

import sys
n = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().split()))
dp = [0]*(n) #1
dp[0] = numbers[0] #2
for i in range(1, n): #3
    dp[i] = max(numbers[i], dp[i-1]+numbers[i]) #4
print(max(dp)) #5

 

#1 : 인덱스 0부터 n-1까지니까 [0]*n으로 해야한다. n+1을 곱하면 #5에서 max값을 출력하는데 입력값이 모두 음수가 있을 수 있어 마지막 원소가 0이 남아 0을 출력해서 틀리게 된다.

#2 : 비교를 위해 첫 원소를 dp에 넣어준다

#3 : 1부터 n-1(여기서는 마지막 원소)까지 비교해 준다.

#4 : 점화식 : 이전까지의 최대값에 지금 인덱스의 값을 더한 값이 더 크면 갱신 그렇게 각 dp의 인덱스마다 최댓값이 저장됨

#5 : dp에 저장된 값중 최대값 출력

 

 

https://hgk5722.tistory.com/189

[백준] 2156 파이썬(python) : 포도주 시식