백준 1912번 누적합 [DP][Python]

문제

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

출력: 33

 

예제 2

10

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

출력: 14

 

문제 링크

---

문제 유형

DP

---

문제 풀이

미리 살펴보는 핵심 포인트 ✅ 

i 번째 데이터까지의 최대 연속합을 기록한다.  sums[i-1]

이 기록한 것을 다음 i 번째 데이터에서 이용해 i 번째 데이터까지의 최대 연속합을 구한다.

 

 

nums[i]는 주어진 배열,

sums[i]는 i번째 인덱스까지 최대 연속합이 담긴 배열이다.

 

i 번째 이전까지의 최대 연속합(sums[i-1])에 i 번째 데이터 값(nums[i]) 을 더해나간다.

단, 이전까지의 최대 연속합(sums[i-1])이 0보다 작으면 이전까지의 누적합을 버리고 ➡️ i 번째 데이터 값(nums[i])을 최대 연속합으로 새로 시작한다.

왜냐하면  이전까지의 최대 연속합과 자신을 더한 것보다, 자기 자신(nums[i])이 더 크기 때문이다.  nums[i] > sums[i-1] + nums[i]

sums[i] = nums[i] +  (sums[i-1] if sums[i-1] > 0 else 0)

# 또는

sums[i] = max(sums[i-1] + nums[i], nums[i])

 

---

하나 하나 해보기

 

🟦 index=0일 때, 현재 위치 기준 최대 연속합은 자기 자신 sums[0] = 10

🟦 index=1일 때, 현재 위치 기준 최대 연속합은 sums[i-1] + nums[i] = 10 + (-12) = -2   ➡️  sums[1] = -2

🟦 index=2일 때,  이전까지의 연속 최대합이 0보다 작으므로,  nums[2] > sums[1] + nums[2]  ➡️ sums[2] = 30

🟦 index=3일 때, 현재 위치 기준 최대 연속합은 sums[i-1] + nums[i] = 30+(-8)  ➡️ sums[3] = 22

 

즉, 현재 위치 기준 최대 연속합은 이전 연속합과 더하거나 더하지 않거나 2가지 중 한 가지가 된다.

 

위를 기반으로 점화식을 만들 수 있으며,

각 부분에서 이전의 결과가 반복적으로 사용되고 해당 최적 결과값이 그대로 사용되니 

DP의 두 가지 조건인 Overlapping Subproblems와 Optimal Substructure를 만족한다.

---

DP 사용하기

1️⃣ DP로 풀 수 있는 문제인지 확인하기

🔽

2️⃣ 문제의 변수 파악하기

정의

: sums[i] = 위치 i에서의 연속합의 최대값

🔽

3️⃣ 점화식 만들기

점화식

sums[i] = nums[i] + (sums[i-1] if sums[i-1] > 0 else 0 )

또는

sums[i] = max(sums[i-1] + arr[i], arr[i])

🔽

4️⃣ 메모하기(Memoization)

sums 배열에 메모되고 있다.

🔽

5️⃣ 기저 상태 파악하기

기저 상태는 첫번째 연속합의 결과를 결정하는 경우일 것이다. 제일 처음은 단순히 그 위치의 원 배열의 숫자가 된다.

기저 상태

: DP[0] = arr[0]

🔽

6️⃣ 구현하기

1) Bottom-Up (Tabulation 방식) - 반복문 사용 ✅
2) Top-Down (Memoization 방식) - 재귀 사용

 

전체 코드

 

 

 

기존 nums에 최대 연속합을 함께 넣어 공간을 재활용할 수도 있다. (공간 복잡도 🔽)

 

 

같은 원리인 아래의 점화식으로도 풀이가 가능하다.

 

 

 

---

참고 출처: [알고리즘 풀이 - 백준 1912(연속합, DP) https://hongjw1938.tistory.com/61

알고리즘 풀이 - 백준 1912(연속합, DP)