[solved.ac 실버2] 1912_연속합 (파이썬, DP)

제한 사항

 

문제

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

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

입력

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

출력

첫째 줄에 답을 출력한다.

예제

---

나의 풀이

이 문제는 누적합을 이용하여 풀었다.

arr = [10, -4, 3, 1, 5, 6, -35, 12, 21, -1]

위 데이터가 주어졌을 때 누적합을 구하면 다음과 같다.

cumulated = [10, 6, 9, 10, 15, 21, -14, -2, 19, 18]

누적합을 구해놨을 때의 장점은 구간 합을 빠르게 구할 수 있다는 점이다.

예를 들어 기존 데이터(arr)의 맨 앞에 있는 10, -4, 3, 1의 합을 구하고 싶다면 cumulated[3]을 확인하면 되고, 3, 4번째의 합을 구하고 싶다면 cumulated[3] - cumulated[1] 을 계산하면 빠르게 구할 수 있다.

이때 구간 합이 최대가 되기 위해서는 최대한 큰 수에서 작은 수를 빼는 경우를 찾아야 한다. 이때 cumulated에서 큰 수가 작은 수보다 오른쪽에 있어야 한다. (구간합의 의미를 생각해보면 왜 그런지 알 수 있다)

 

시간 초과

n = int(input())
arr = list(map(int, input().split()))
cumulated = [arr[0]]  # 누적 합
for i in range(1, n):
    cumulated.append(cumulated[-1] + arr[i])

d = cumulated[:]  # 누적 합 복제

for i in range(n):
    for j in range(i):
        d[i] = max(d[i], cumulated[i] - cumulated[j])
print(max(d))

위 코드는 처음에 제출했던 코드이다. 결과는 [시간 초과]로 실패했다.

i번째 인덱스에서 최선의 값을 찾아서 d[i]에 저장하고, 최종적으로 d에 저장된 값 중 가장 큰 값을 찾는 로직이었는데 최악의 경우 O(n^2) -> 10,000,000,000 이상의 반복이 필요할 수 있다. 시간 제한 1초 안에 들어오기 힘든 수치다.

 

정답 코드

n = int(input())
arr = list(map(int, input().split()))
cumulated = [arr[0]]  # 누적 합
for i in range(1, n):
    cumulated.append(cumulated[-1] + arr[i])

d = cumulated[:]  # 누적 합 복제

min_idx = 0
answer = d[0]
for i in range(1, n):
    d[i] = max(d[i], d[i] - cumulated[min_idx])
    if i < n - 1 and cumulated[i] < cumulated[min_idx]:
        min_idx = i
    if d[i] > answer:
        answer = d[i]
print(answer)

위 실패 코드처럼 매번 케이스를 현재 위치보다 작은 구간에서 최소 값을 찾는 것이 아니라 한 번 찾아둔 최소 값을 가지고 가다가 더 작은 값을 발견하면 그 때 갱신하는 식으로 하여 이중 for문을 한 겹 벗겨낼 수 있었다.

그리고 i가 n - 1 일 때도 갱신하게 되면 누적합 리스트의 제일 끝에 최소 값이 존재할 때 자기 자신을 빼서 0이 나오게 된다. 위에서 말한 누적 합을 활용하는 방법을 생각해보면 왜 제일 끝에서는 최소 값을 갱신하면 안 되는지 알 수 있을 것이다.

 

채점 결과