백준 1912번 연속합

문제 링크

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

풀이 전 계획과 생각

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

그러니까 수 하나 이상은 반드시 선택해야 한다. 수열에 음수만 있다고 해서 그냥 하나도 안 더하고 0! 이럴 수는 없다.
그리고 연속으로 더하는 것만 가능하고 뛰어넘어서 큰 수 아무거나 골라서 더하는 건 안 된다.

이 문제는 동적 프로그래밍이 무엇인지 알기만 하면 어렵지 않은 편이다. 현재의 연속합 최댓값을 입력하는 배열을 따로 만들어 놓고 거기에 입력된 값 중에서 최댓값을 출력하면 된다.

그리고 현재의 연속합이란 무엇인가? 이 수열에서 덧셈은 두 가지 방법만 가능하다. 즉 직전의 연속합에 연속해서 더하거나 직전의 연속합이 음수라면 더하지 않고 지금 현재의 값부터 0에 더하기 시작하는 것이다.

그러면 그 다음 수에서 무엇을 더할지도 직전의 연속합 값으로만 쉽게 구할 수 있다.

풀이 (코드 블록 첨부)

import sys
N = int(sys.stdin.readline())
sequence = list(map(int,list(sys.stdin.readline().split())))
#print(sequence)
current_max = [0 for x in range(N)]
#print(current_max)
current_max[0] = sequence[0]
max_output = current_max[0]
for i in range(1,N):
    current_max[i] = max(current_max[i-1]+sequence[i], sequence[i])
    if max_output<current_max[i]:
        max_output=current_max[i]
print(max_output)

풀이하면서 막혔던 점과 고민

앞의 다른 동적 프로그래밍 문제들처럼 '연속'의 정의가 까다롭거나 두 개 연속만 가능하거나 한 게 아니라서 직전과 연속하느냐 단절하느냐 두 가지만 있으니까 어려움이 없었다. 반드시 하나의 수는 더해야 한다는 점만 기억하고 첫번째 칸의 연속합 최댓값은 첫번째 칸의 값을 반드시 입력해야 하고 0을 선택할 수 없다는 점만 잘 기억하면 실수 없이 한 번에 합격할 수 있다.

풀이 후 알게된 개념과 소감

그래도 합격률이 그렇게 높지 않던데 지금까지 동적 프로그래밍 문제 네 개를 풀어봤기 때문에 익숙해서 쉽게 푼 거겠지? 그래도 가끔 이렇게 쉽게 합격할 때도 있어야지. ㅋㅋㅋ