[실버 II] 1912번. 연속합

 문제 

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

1912번: 연속합

 사용 언어 

Python3

 풀이 과정 

또다른 동적계획법 문제! 처음에는 아래 제출 방식대로 제출했다가 아래와 같이 수정해봤는데 append를 사용하는게 조금은 더 시간이 걸리는 것을 확인했다.

from sys import stdin

input = stdin.readline
n = int(input())
sequence = list(map(int, input().split()))

maxSum = []
final_max = sequence[0]
maxSum.append(sequence[0])
for n in range(1, len(sequence)):
    maxSum.append(max(maxSum[n-1], 0) + sequence[n])
    if final_max < maxSum[n]:
        final_max = maxSum[n]

print(final_max)

문제를 이해하고 어떻게 풀어야 할지 감 잡는데 좀 시간이 걸렸던 문제인데

음수가 있어서 이전 숫자까지의 최대 합과 0을 비교해서 더 큰 값에 새로운 숫자를 더하는 로직을 생각해내는 것이 포인트였다.

 제출 답안 

from sys import stdin

input = stdin.readline
n = int(input())
sequence = list(map(int, input().split()))

sum = [0] * n
sum[0] = sequence[0]

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

print(max(sum))

 다른 사람 답안 

아무래도 더 간결한 답안이 있을 것 같아 배울 점이 있는 코드를 찾아보았다.

아래 코드는 내 코드랑 메모리는 똑같지만 108ms가 걸렸는데 선언을 하지 않고 바로 for문을 돌린 점..?이 다른 것 같다.

import sys

if __name__ == '__main__':
    _ = sys.stdin.readline()
    arr = list(map(int, sys.stdin.readline().rstrip('\n').split(' ')))
    for i in range(1, len(arr)):
        if arr[i - 1] > 0: arr[i] += arr[i - 1]

    print(max(arr))

출처: https://home-body.tistory.com/546