[P5] 백준 2104번 부분배열 고르기 C++ 세그먼트 트리

리뷰

 

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

구간의 누적합과 최소값의 인덱스를 저장한 세그먼트 트리를 구현하고 구간의 누적합 * 구간의 최소값이 가장 큰 케이스를 찾아 출력하는 문제

 

 

전역 변수

• n :주어지는 배열의 길이
• MAX_N : n의 최대값
• nodes : 배열 정보를 저장할 정수형 배열, 크기는 MAX_N으로 세팅한다.
• minTree : 최소값의 인덱스를 저장할 세그먼트 트리 크기는 MAX_N * 4
• sumTree : 구간의 합을 저장할 세그먼트 트리 크기는 MAX_N * 4

 

함수

1. minBuild

void minBuild(ll node, ll s, ll e)

 

minTree를 초기화 하기 위한 함수

1. 리프 노드에 s혹은 e로 각 배열의 인덱스를 저장해 준다.
2. 리프 노드가 아닐 경우 s + e / 2를 변수 mid에 저장한다.
3. mid를 기준으로 왼쪽 오른쪽 자식 노드를 재귀를 통해 초기화를 진행한다.
4. 트리의 노드는 왼쪽 오른쪽 자식의 배열내 값이 작은 것의 인덱스를 저장해 주면 된다.

 

2. sumBuild

void sumBuild(ll node, ll s, ll e)

 

sumTree를 초기화 하기 위한 함수

1. 모든 내용은 1. minBuild와 유사하나 해당 함수는 리프 노드에 배열의 s혹은 e의 값을 저장한다.
2. 또한 노드는 왼쪽 자식 노드와 오른쪽 자식 노드의 합으로 초기화 한다.

 

3. getIndex

ll getIndex(ll node, ll s, ll e, ll L, ll R)

 

구간의 최소값을 가지는 노드의 인덱스를 추출하는 함수

1. 기저조건으로는 범위를 벗어나면 -1를 리턴한다, 범위가 일치하면 minTree의 노드를 리턴한다.
2. 기저조건에 해당하지 않는다면 mid에 s + e / 2를 저장해 준다.
3. left, right에 각각 재귀를 진행하여 최소값의 인덱스를 찾아준다.
4. 만약 left가 -1이라면 right를, right가 -1이라면 left를 리턴해 준다.
5. 둘 다 -1이 아니라면 left, right 중 배열 내의 값이 더 작은 것의 인덱스를 리턴해 준다.

 

4. sumQuery

ll sumQuery(ll node, ll s, ll e, ll L, ll R)

 

구간의 합 정보를 출력하기 위한 함수

1. 일반적인 세그먼트 트리의 구간합을 구하는 쿼리문과 동일하다.

 

5. minQuery

ll minQuery(ll s, ll e)

 

구간의 최소값을 구하고, 구간합과 최소값의 곱셈을 리턴하는 함수

1. 매개변수로 탐색할 범위 s, e를 받아준다.
2. s가 e보다 클 경우 0을 리턴해 준다.
3. getIndex 함수를 통해 구간 최소값의 인덱스를 min_index 변수에 저장해 준다.
4. 배열의 min_index 값과 구간합을 sumQuery로 구해주어 곱한 값을 all에 저장한다.
5. left, right에 각각 minQuery를 재귀호출하여 최대 값을 저장해 준다.
6. all, left, right 중 가장 큰 값을 리턴한다.

 

문제풀이

1. n값을 입력 받고, nodes배열에 n개의 정수를 입력 받는다.
2. minBuild함수를 통해 minTree를 초기화 해준다.
3. sumBuild함수를 통해 sumTree를 초기화 해준다.
4. minQuery를 0 ~ n - 1범위로 호출하여 나온 리턴값을 출력해 준다.

 

참고 사항

최악의 경우 1,00,000,000,000 * 1,000,000이므로 long long타입으로 설정해 주어야 한다.

 

 

정답 코드

#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;

ll n;
const ll MAX_N = 100000;
ll nodes[MAX_N];
ll minTree[MAX_N * 4];
ll sumTree[MAX_N * 4];

void minBuild(ll node, ll s, ll e) {
	if (s == e) minTree[node] = s;
	else {
		ll mid = (s + e) / 2;
		minBuild(node * 2, s, mid);
		minBuild(node * 2 + 1, mid + 1, e);
		minTree[node] = nodes[minTree[node * 2]] <= nodes[minTree[node * 2 + 1]] ? minTree[node * 2] : minTree[node * 2 + 1];
	}
}

void sumBuild(ll node, ll s, ll e) {
	if (s == e) sumTree[node] = nodes[s];
	else {
		ll mid = (s + e) / 2;
		sumBuild(node * 2, s, mid);
		sumBuild(node * 2 + 1, mid + 1, e);
		sumTree[node] = sumTree[node * 2] + sumTree[node * 2 + 1];
	}
}

ll getIndex(ll node, ll s, ll e, ll L, ll R) {
	if (R < s || e < L) return -1;
	if (L <= s && e <= R) return minTree[node];
	ll mid = (s + e) / 2;
	ll left = getIndex(node * 2, s, mid, L, R);
	ll right = getIndex(node * 2 + 1, mid + 1, e, L, R);

	if (left == -1) return right;
	if (right == -1) return left;
	return nodes[left] <= nodes[right] ? left : right;
}

ll sumQuery(ll node, ll s, ll e, ll L, ll R) {
	if (R < s || e < L) return 0;
	if (L <= s && e <= R) return sumTree[node];
	ll mid = (s + e) / 2;
	ll left = sumQuery(node * 2, s, mid, L, R);
	ll right = sumQuery(node * 2 + 1, mid + 1, e, L, R);

	return left + right;
}

ll minQuery(ll s, ll e) {
	if (s > e) return 0;
	ll min_index = getIndex(1, 0, n - 1, s, e);
	ll all = nodes[min_index] * sumQuery(1, 0, n - 1, s, e);
	ll left = minQuery(s, min_index - 1);
	ll right = minQuery(min_index + 1, e);
	return max({ all, left, right });
}

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

	cin >> n;
	for (ll i = 0; i < n; i++) cin >> nodes[i];
	minBuild(1, 0, n - 1);
	sumBuild(1, 0, n - 1);
	cout << minQuery(0, n - 1);
}