이번에는 백준 1912번 연속합 문제를 풀어보았습니다.
현재까지의 연속합을 유지하다가 음수가 되는 순간 버리고 다시 시작하는 방식으로 해결할 수 있습니다.
문제 설명
정수로 이루어진 수열이 주어집니다.
이 중에서 연속된 하나 이상의 수를 선택하여 만들 수 있는 합 중 가장 큰 값을 구하는 문제입니다.
반드시 하나 이상의 수를 선택해야 합니다.
풀이 아이디어
연속된 구간의 합을 계속 유지하며 계산합니다.
현재까지의 합을 sum이라고 할 때,
- 현재 숫자를 더한 뒤
ret을 갱신합니다. - 만약
sum이 음수가 되었다면 이후의 연속합에는 도움이 되지 않으므로0으로 초기화합니다.
음수인 구간을 계속 가져가는 것보다 다음 숫자부터 새롭게 시작하는 것이 항상 더 유리하기 때문입니다.
코드
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
int ret = -1004;
cin >> n;
int sum = 0;
for (int i=0; i<n; i++) {
int num;
cin >> num;
sum += num;
ret = max(ret, sum);
if (sum < 0) sum = 0;
}
cout << ret;
return 0;
}풀이 흐름
-
수열의 길이를 입력받습니다.
-
현재 연속합을 저장하는
sum을 0으로 초기화합니다. -
수를 하나씩 입력받으며 현재 연속합에 더합니다.
-
현재 연속합과 기존 최댓값을 비교하여
ret을 갱신합니다. -
현재 연속합이 음수가 되면
sum을 0으로 초기화합니다. -
모든 수를 확인한 뒤 최댓값을 출력합니다.
구현 포인트
1. 현재 연속합 관리
int sum = 0;sum은 현재 선택하고 있는 연속 구간의 합을 의미합니다.
새로운 숫자를 읽을 때마다
sum += num;을 수행하여 현재 연속합을 계속 유지합니다.
2. 최댓값 갱신
ret = max(ret, sum);현재 연속합이 지금까지의 최댓값보다 크다면 답을 갱신합니다.
매 숫자를 읽을 때마다 수행하므로 모든 가능한 연속 구간의 최댓값을 확인할 수 있습니다.
3. 연속합이 음수가 되면 버리기
if (sum < 0)
sum = 0;현재 연속합이 음수가 되었다면 이후의 연속 구간에 포함시키는 것은 항상 손해입니다.
예를 들어
현재 합 = -5
다음 숫자 = 10이라면
-5 + 10 = 5보다
10부터 새롭게 시작하는 것이 더 큰 값을 만들 수 있습니다.
따라서 음수가 된 순간 현재 구간을 버리고 다음 숫자부터 다시 시작합니다.
4. 모든 수가 음수인 경우
int ret = -1004;최댓값을 매우 작은 값으로 초기화한 이유는 모든 수가 음수인 경우를 처리하기 위해서입니다.
예를 들어
-3 -7 -1이라면 정답은 -1입니다.
만약 ret을 0으로 초기화하면 잘못된 결과가 나오므로 입력 범위보다 작은 값으로 초기화하였습니다.
5. Kadane 알고리즘
이 문제는 대표적인 Kadane 알고리즘을 사용하는 문제입니다.
핵심 아이디어는 다음 한 줄입니다.
현재까지의 연속합이 음수가 되면 버리고 새롭게 시작한다.이를 반복하면 모든 연속 부분합을 직접 계산하지 않고도 최댓값을 구할 수 있습니다.
시간복잡도
수열을 한 번만 순회합니다.
따라서 시간복잡도는
O(N)입니다.
추가적인 배열도 사용하지 않으므로 공간복잡도는
O(1)입니다.
