백준 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번째 인덱스에 대해 쿼리를 수행하면 답을 구할 수 있습니다.

 

 

개발환경:Visual Studio 2022

 

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