[백준/BOJ] python 1912번 연속합

언어: python

번호: 1912

제목: 연속합

등급: 실버 2

 

 

풀이 과정:

DP를 이용한다. 숫자들을 리스트로 입력받고, for문으로 리스트를 돌면서 최댓값만 저장한다.  

​dp[i] =max(arr[i], dp[i-1] + arr[i])

점화식은 위와 같다. 연속된 합을 구해야하기 때문에 여태까지 더한 값보다 더 큰 값을 만나면, 최댓값이 바뀌는 것이다. 이렇게 모인 최댓값들 중에 가장 큰 값을 출력하면 된다. 

​

 

코드:

# 1912
n = int(input())
arr = list(map(int, input().split())
dp = [0] * n
dp[0] = arr[0]

for i in range(1, n):
	dp[i] = max(arr[i], dp[i-1] + arr[i])

print(max(dp))

 

 

메모:

Dynamic Programing, 동적 계획법

값을 저장해 재사용하면서 효율적으로 계산하는 알고리즘이다. 복잡한 문제를 여러개의 간단한 문제로 나누어 계산하며 두가지 조건이 있다.

1) 큰 문제를 작은 문제로 나누었을때 겹치는 부분이 있어야 한다.
2) 부분 문제의 최적값을 사용해 큰 문제의 최적 결과를 낼 수 있어야 한다.