[백준 30646] 최대 합 순서쌍의 개수 (C++)

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

 

문제

---

크기가 N인 배열 a가 주어진다. 배열 a의 임의의 위치를 나타내는 두 수 i, j를 골랐을 때, 아래 두 조건을 만족하면 같은 수 순서쌍 (i, j)를 만들 수 있다.

• 1 ≤ i ≤ j ≤ N
• a_i = a_j

만들어진 같은 수 순서쌍 (i, j)의 합은 a_i부터 a_j까지의 합 a_i + a_i+1 + a_i+2 + … + a_j-1 + a_j로 정의된다. 이때 주어진 배열에서 만들 수 있는 같은 수 순서쌍의 최대 합을 찾고, 최대 합을 가지는 같은 수 순서쌍의 개수를 출력하는 프로그램을 작성하시오.

입력

---

첫 번째 배열 a의 크기 N이 주어진다.

두 번째 줄에 배열 a의 원소 a₁, a₂, …, a_N이 주어진다.

 

출력

---

주어진 배열에서 만들 수 있는 같은 수 순서쌍의 최대 합과 최대 합을 가진 같은 수 순서쌍의 개수를 출력한다.

 

제한

---

• 1 ≤ N ≤ 200,000
• 1 ≤ a_i ≤ 10⁹

문제 풀이

---

부분 합을 이용하는 문제.

배열의 각 수와 이 수를 가진 인덱스들을 모아놓는 map<int, vector<int>>을 사용한다. a_i는 1보다 크거나 같으므로 a_i = a_j이면서 최대 합을 가지려면 벡터의 맨 앞(=해당 수를 가지는 첫번째 인덱스)와 벡터의 맨 뒤(=해당 수를 가지는 맨 마지막 인덱스)만을 가져와 해당 구간의 합을 구하면 된다.

 

 

아래는 코드.

#include <iostream>
#include <map>
#include <vector>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;
	int* arr = new int[N];
	long long* sums = new long long[N+1];
	map<int, vector<int>> m;
	map<int, vector<int>>::iterator it;
	sums[0] = 0;
	long long maxSum = 0;
	long long maxSumCount = 0;
	for (int i = 1; i < N+1; i++)
	{
		cin >> arr[i-1];
		it = m.find(arr[i - 1]);
		if (it == m.end())
		{
			vector<int> v;
			v.push_back(i - 1);
			m.insert({ arr[i - 1], v });
		}
		else
		{
			it->second.push_back(i - 1);
		}
		sums[i] = sums[i - 1] + arr[i - 1];
	}
	for (map<int, vector<int>>::iterator it = m.begin(); it != m.end(); it++)
	{
		int firstIndex = it->second.front();
		int lastIndex = it->second.back();
		long long partSum = sums[lastIndex + 1] - sums[firstIndex];
		if (partSum > maxSum)
		{
			maxSum = partSum;
			maxSumCount = 1;
		}
		else if (partSum == maxSum)
		{
			maxSumCount++;
		}
	}
	cout << maxSum << " " << maxSumCount << "\n";
	return 0;
}