[Python] 백준 풀기 1912 - 연속합

파이썬 백준 1912번

실버2

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

1912번: 연속합

 

 

 

문제 보기

분류: 다이나믹 프로그래밍

 

 

 

문제 풀기

구간합의 최대치가 되기 위해서는 최대한 양수를 누적 시켜나가야 한다. 이에 반하여 최대값에 문제가 되는 경우는 누적합이 음수가 나올때이다. 양의 정수로 이루어진 누적합은 앞으로 나올 수와 합해져 오르락 내리락 할테지만 (누적 합이 0 이상 일때) 최대값에 기여를 할 수 있다. 하지만 음의 정수로 누적합을 기록하는 순간 그 묶음은 최대값의 후보에서 제외될 수 밖에 없다.

이것을 이용하여 주어진 숫자들을 하나 하나 더해 나가면서 그 또한 하나 하나 저장해 나간다. 이 때, 누적 합이 음수가 나오는 시점에는 다음에 등장하는 숫자부터 다시 시작하여 누적합을 진행한다.

이번 문제에서 다이나믹 프로그래밍을 위한 코드 형식으로는

sum_array[i] = sum_array[i - 1] + num_sequence[i]

이 사용되었다.

 

 

 

코드 보기

import sys
inputdata = sys.stdin.readline

def fnMaximumSum(num_sequence, sum_array):
    for i in range(len(num_sequence)):
        if i == 0:
            sum_array[0] = num_sequence[0]
        elif sum_array[i - 1] < 0:
            sum_array[i] = num_sequence[i]
        else:
            sum_array[i] = sum_array[i - 1] + num_sequence[i]
    print(f'sum_array: {sum_array}')            # test print
    return max(sum_array)


if __name__ == "__main__":
    n = int(inputdata().strip())
    num_sequence = list(map(int, inputdata().split()))
    print(f'num_sequence: {num_sequence}')         # test print
    
    sum_array = [None] * n
    result = fnMaximumSum(num_sequence, sum_array)
    
    print(result)



# 10
# 10 -4 3 1 5 6 -35 12 21 -1

# num_sequence: [10, -4, 3, 1, 5, 6, -35, 12, 21, -1]
# sum_array: [10, 6, 9, 10, 15, 21, -14, 12, 33, 32]

# 33