백준 27989번 가장 큰 증가하는 부분 수열 2

문제 링크입니다: https://www.acmicpc.net/problem/27989

 

맥스 펜윅 트리를 활용하는 문제였습니다.

 

알고리즘은 다음과 같습니다.

1. cache는 수열 A를 오름차순으로 정렬한 배열입니다.

2. 수열 A를 순회하며 이분탐색을 통해 현재 A[i]가 cache에 위치한 인덱스를 찾습니다.

2.1 +1을 하는 이유는 A는 0-인덱스인 반면 펜윅 트리는 1-인덱스이기 때문입니다.

3. A[i]보다 작은 모든 값들에 대해 현재까지 계산된 최대 부분합을 구합니다.

4. 3번에서 구한 값과 A[i]를 합치면 현재 인덱스까지의 최대 부분합을 구할 수 있습니다. 해당 값을 펜윅 트리의 idx 위치에 업데이트합니다.

5. 2 ~ 4번 과정을 반복한 뒤 N번째 인덱스에 대해 쿼리를 수행하면 답을 구할 수 있습니다.

 

	#include <iostream>
	#include <cstring>
	#include <algorithm>
	using namespace std;
	const int MAX = 3e5 + 3e2;
	int N;
	long long A[MAX];
	long long cache[MAX];
	long long tree[MAX];
	void update(int idx, long long value)
	{
	while (idx <= N)
	{
	tree[idx] = max(tree[idx], value);
	idx += idx & -idx;
	}
	}
	long long query(int idx)
	{
	long long result = 0;
	while (idx)
	{
	result = max(result, tree[idx]);
	idx -= idx & -idx;
	}
	return result;
	}
	int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++)
	{
	cin >> A[i];
	cache[i] = A[i];
	}
	sort(cache, cache + N);
	for (int i = 0; i < N; i++)
	{
	int idx = lower_bound(cache, cache + N, A[i]) - cache + 1;
	long long pSum = query(idx - 1);
	update(idx, pSum + A[i]);
	}
	cout << query(N) << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

 

개발환경:Visual Studio 2022

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~