[BOJ/Gold 4] 백준 2313 보석 구매하기(C++)

문제 링크

https://www.acmicpc.net/problem/2313

2313번: 보석 구매하기

 

문제

보석 가게에 여러 가지의 보석이 진열되어 있다. 각각의 보석은 정수로 표현되는 가치가 있다. 때로는 저주받은 보석이 있기 때문에 가치가 음수가 될 수도 있다.

보석들은 총 n개의 줄에 나열되어 있다. 이제 당신은 각각의 줄에서 몇 개의 보석을 구매하려 한다. 이때, 각 줄에서 보석을 구매할 때 연속적인 보석들을 구매해야 한다. 즉, 어느 한 줄에서 1, 2번 보석을 구매할 수도 있고, 2, 3번 보석을 구매할 수도 있지만, 1, 3번 보석을 구매할 수는 없다.

구매하는 보석의 가치의 총 합이 최대가 되도록 보석을 구매하는 방법을 찾아내는 프로그램을 작성하시오.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 1,000)이 주어진다. 다음 2×n개의 줄에는 n개의 줄에 나열된 보석들에 대한 정보가 주어진다. 먼저 각 줄에 나열된 보석의 개수 L(1 ≤ L ≤ 1,000)이 주어지고, 그 다음 줄에 L개의 정수들이 주어진다. 각 정수는 각 보석의 가치를 나타낸다. 보석의 가치는 절댓값이 10,000보다 작거나 같은 정수이다.

출력

첫째 줄에 보석의 가치의 총 합의 최댓값을 출력한다. 다음 n개의 줄에는, 줄에서 몇 번째 보석부터 몇 번째 보석까지를 구매했는지를 출력한다.

만약 최대가 되는 경우가 여럿이면, 구매한 보석들의 총 개수가 최소가 되는 방법을 출력한다. 이와 같은 경우도 여럿이라면, 출력한 n×2개의 수들을 하나의 수열로 생각하여, 사전식으로 가장 앞에 오는 경우를 출력한다.

예제 입력 1

2
5
30 70 -10 10 0
9
90 80 70 60 0 -60 0 60 -60

예제 출력 1

400
1 2
1 4

알고리즘 분류

• 누적 합

풀이

N개의 나열된 보석마다 누적 합을 구하고, N개의 나열된 보석마다 연속적인 가치가 최대가 되는 보석의 구간을 구한다.

이 때, 구간의 시작점이 1번인 보석부터 차례대로 탐색하기 때문에 사전식으로 탐색하게 된다.

만약에 기록된 최댓값과 현재 구간의 보석의 가치의 최댓값이 같은 경우, 구간에 포함된 보석의 개수가 더 적은 구간이 답이 된다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <ctime>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 1001
#define LL long long
#define INF 1e9

using namespace std;
int N;
int L[MAX];
int Sum[MAX][MAX];
int Answer = 0;
pair<int, int> AnswerTwin[MAX];

void Input() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> L[i];
		for (int j = 1; j <= L[i]; j++) {
			int X;
			cin >> X;
			Sum[i][j] = Sum[i][j - 1] + X;
		}
	}
}

void Settings() {
	for (int i = 1; i <= N; i++) {
		int Big = -INF;
		for (int j = 1; j <= L[i]; j++) {
			for (int k = j; k <= L[i]; k++) {
				int Cur = Sum[i][k] - Sum[i][j - 1];
				if (Big < Cur) {
					Big = Cur;
					AnswerTwin[i] = make_pair(j, k);
				}
				else if (Big == Cur) {
					if ((AnswerTwin[i].second - AnswerTwin[i].first) > (k - j)) {
						AnswerTwin[i] = make_pair(j, k);
					}
				}
			}
		}
		Answer += Big;
	}
}

void Find_Answer() {
	cout << Answer << "\n";
	for (int i = 1; i <= N; i++) {
		cout << AnswerTwin[i].first << " " << AnswerTwin[i].second << "\n";
	}
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}