[Python] BOJ(백준) 1912번 - 연속합

1. 링크

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

2. 난이도(solved.ac 참고)

실버2

3. 풀이

	# https://www.acmicpc.net/problem/1912
	n = int(input())
	a = list(map(int, input().split()))
	dp = [0] * n
	dp[0] = a[0]
	if max(a) < 0:
	print(max(a))
	else:
	for i in range(1, n):
	if dp[i-1] + a[i] > 0:
	dp[i] = dp[i-1] + a[i]
	print(max(dp))

view raw 연속합.py hosted with ❤ by GitHub

가장 큰 값이 음수라면 일단 더해봤자 값이 더 커질 수가 없으므로 그 값만 출력한다.

 

그게 아닐 경우에는 dp라는 배열을 따로 만들어서 첫 값으로는 input값을 받아서 만든 리스트의 첫번째 값을 반환하고 그 이후부터는 dp의 이전 인덱스 값과 input값을 받아서 만든 리스트 a의 현재 인덱스 값을 더한 게 양수인 경우에만 dp의 현재 인덱스에 값을 부여해주고 그게 아니라면 dp[i]는 0으로 그대로 남게 된다. 즉 더한 값이 0보다 작을 경우엔 0으로 초기화하여 다시 시작하는 과정을 반복한 것이다.