문제
보석 가게에 여러 가지의 보석이 진열되어 있다. 각각의 보석은 정수로 표현되는 가치가 있다. 때로는 저주받은 보석이 있기 때문에 가치가 음수가 될 수도 있다.
보석들은 총 n개의 줄에 나열되어 있다. 이제 당신은 각각의 줄에서 몇 개의 보석을 구매하려 한다. 이때, 각 줄에서 보석을 구매할 때 연속적인 보석들을 구매해야 한다. 즉, 어느 한 줄에서 1, 2번 보석을 구매할 수도 있고, 2, 3번 보석을 구매할 수도 있지만, 1, 3번 보석을 구매할 수는 없다.
구매하는 보석의 가치의 총 합이 최대가 되도록 보석을 구매하는 방법을 찾아내는 프로그램을 작성하시오.
입력
첫째 줄에 정수 n(1 <= n <= 1,000)이 주어진다. 다음 2xn개의 줄에는 n개의 줄에 나열된 보석들에 대한 정보가 주어진다. 먼저 각 줄에 나열된 보석의 개수 L(1 <= L <= 1,000)이 주어지고, 그 다음 줄에 L개의 정수들이 주어진다. 각 정수는 각 보석의 가치를 나타낸다. 보석의 가치는 절댓값이 10,000보다 작거나 같은 정수이다.
출력
첫째 줄에 보석의 가치의 총 합의 최댓값을 출력한다. 다음 n개의 줄에는, 줄에서 몇 번째 보석부터 몇 번째 보석까지를 구매했는지를 출력한다.
만약 최대가 되는 경우가 여럿이면, 구매한 보석들의 총 개수가 최소가 되는 방법을 출력한다. 이와 같은 경우도 여럿이라면, 출력한 nx2개의 수들을 하나의 수열로 생각하여, 사전식으로 가장 앞에 오는 경우를 출력한다.
풀이
각 가게는 독립적이므로, 결국 매 수열마다 최대 부분 배열을 한 번씩 구하면 된다. 코드에서는 카데인 알고리즘 형태로 curSum을 유지하면서 최대 합 구간을 찾는다.
현재 누적합이 0 이하가 되면 새로 시작하는 편이 유리하므로 시작점을 현재 위치로 옮긴다. 최대 합이 갱신되면 구간을 바꾸고, 같은 합이면 길이가 더 짧은 구간을 선택한다.
각 수열의 최대 합을 총합에 더하고, 고른 구간 인덱스를 따로 저장해 마지막에 한 번에 출력한다.
코드
#include <iostream>
#include <vector>
using namespace std;
int L;
long long totalAnsSum;
int store[1000];
vector<pair<int, int>> ansIdx;
void solve() {
vector<int> sum(L);
sum.push_back(store[0]);
int start = 0, end = 0, cur = 0;
long long maxSum = store[0];
long long curSum = store[0];
for (int i = 1; i < L; i++) {
if (curSum <= 0) {
curSum = store[i];
cur = i;
}
else {
curSum += store[i];
}
if (curSum > maxSum) {
maxSum = curSum;
start = cur;
end = i;
}
else if (curSum == maxSum) {
int len = i - cur + 1;
int min_len = end - start + 1;
if (len < min_len) {
start = cur;
end = i;
}
}
}
totalAnsSum += maxSum;
ansIdx.push_back(make_pair(start + 1, end + 1));
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
for (int i = 0; i < N; i++) {
cin >> L;
for (int j = 0; j < L; j++)
cin >> store[j];
solve();
}
cout << totalAnsSum << '\n';
for (auto idx : ansIdx)
cout << idx.first << " " << idx.second << '\n';
return 0;
}복잡도
- 시간 복잡도: 각 수열 길이의 합에 대해
- 공간 복잡도:
마무리
결국 가게마다 최대 부분 배열을 구하는 문제다. 같은 최대 합일 때 더 짧은 구간을 고르는 추가 조건만 놓치지 않으면 된다.
