[백준][동적 계획법 1] No.1912_연속합 01

1912번: 연속합

임의의 수열이 주어졌을 때, 가장 큰 연속된 수의 합을 산출하라는 문제이다.

여기서 핵심은 연속하는 길이가 얼마인지, 가장 큰 값이 얼마인지 아예 모른다는 것이다.

그래서 처음에는 길이를 1에서부터 임의의 수열만큼 for문을 돌리고

거기서 계속 더하는 방식을 생각했다.

 

# 위에서 언급한 방법 의사 코드

for LEN in range(1, len(arr)+1):				# 연속된 수의 길이
	for INDEX in range(len(arr) - LEN):		# 연속된 수의 합 시작점
    		for문으로 LEN 길이만큼 더하기		# 연속된 수 더하기
            		if MAXNUM = 가장 큰 값		# 가장 큰 값 판별하기

 음...이건 아니다. 이렇게만 봐도 시간복잡도가 O(n⁴)를 넘는다.

이건 동적 계획법이 아니라 브루트 포스에 더 가깝다. 조금 더 세련된 방법이 필요하다.

동적 계획법은 작은 문제로 나누어, 과거에 구한 값을 활용하는 방식임을 생각해보자.

 

우선 가장 큰 값을 활용해야 하니, 어떤 두 값을 비교하여 최댓값을 저장한다.

그리고 이 최댓값을 불러와서 다시 비교한다.

이런 식으로 작성하면 될 것 같은 느낌이 들었다.

 

for i in arr:
	tmp[i] = tmp[i-1]+arr[i]와 arr[i] 중 더 큰 값

여기서 핵심은 과거에 구한 값을 활용하는 것이다.

이전의 값들을 더해서 tmp에 저장하고, 그것을 새로운 값과 비교하여 다시 더한다.

이렇게 하면 계속해서 연속된 값을 유지할 수 있다.

 

# ---------- Import ----------
import sys
input = sys.stdin.readline

# ---------- Main ----------
N = int(input())
cache = [-1001] * (N+1)

list_N = [0] + list(map(int, input().split()))

for i in range(1, N+1):
    cache[i] = max(list_N[i], list_N[i] + cache[i-1])
    
print(max(cache))

# ---------- Comment ----------
# max(list_N[i], list_N[i] + cache[i-1])
# 이제껏 더한 수와, 현재 배열의 수 중 더 큰 값을 찾는다.

이런 식으로 작성하면 연속된 값들 중 가장 큰 값을 얻을 수 있다.

처음에 연속하는 길이가 얼마인지에 대한 고민을 조금 많이 했었는데 별로 중요하지 않았다.

결국 중요한 것은 출력이 가장 큰 값이다.

 

주어진 입력은 list_N에 저장하였고, 임의로 저장하는 배열은 cache로 선언했다.

list_N의 0번째 인덱스를 0을 넣어준 이유는 계산을 편하게 하기 위함이다.

cache를 -1001로 초기화한 이유는 조건이 "수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다."이기 때문이다.

 

이를 알기 쉽게 그림으로 그리면 위와 같다.