[Baekjoon] 1912. 연속합

문제 설명

문제

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

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1

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

예제 출력 1

33

예제 입력 2

10
2 1 -4 3 4 -4 6 5 -5 1

예제 출력 2

14

예제 입력 3

5
-1 -2 -3 -4 -5

예제 출력 3

-1

문제 풀이

# 다이나믹 프로그래밍

unsorted list 에서 연속합의 최댓값을 구하는 문제입니다.

처음에는 i번째 수부터 j번째 수까지의 합을 저장하는 dp[ i ][ j ] 배열로 풀이하려 했지만, 메모리 초과가 발생했습니다…

n = int(input())
nums = list(map(int, input().split()))
sums = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    for j in range(i,n):
        sums[i][j] = sums[i][j-1] + nums[j]
print(max([max(sums[n][i:]) for n,i in enumerate(range(n))]))

생각해보니, 위의 풀이에서는 굳이 필요하지 않은 메모리가 발생하므로 그것을 없애주려 했습니다.

그래서 아래와 같은 풀이로 바꿨더니..!!! 역시나 메모리 초과…

n = int(input())
nums = list(map(int, input().split()))
sums = [[0 for _ in range(n-i)] for i in range(n)]
for i in range(n): # i 번째 수
    for j in range(n-i): # i+j 번째 수
        sums[i][j] = sums[i][j-1] + nums[i+j]
print(max([max(sum) for sum in sums]))

그래서 접근 방법을 아예 바꿔야겠다고 생각했습니다.

모든 연속합들을 저장한 뒤 최댓값을 찾는 것이 아니라, 각 위치에서의 최대 연속합을 바로 구하면 되는 것이었습니다.

n = int(input())
nums = list(map(int, input().split()))
sums = [0 for _ in range(n)]
sums[0] = nums[0]
for i in range(1,n):
    sums[i] = max(nums[i],sums[i-1]+nums[i])
print(max(sums))

sums 리스트의 i번째 원소는 ? ~ i번째 수(nums의 i번째 원소)까지의 최대 연속합을 나타냅니다.

이 때 i번째 원소는 반드시 포함합니다.

우리의 목적은 최대 연속합을 구하는 것이기 때문에, 위의 풀이를 사용하면 메모리 뿐만 아니라 시간 복잡도도 O(n)으로 줄어듭니다.