알고리즘/문제풀이

[백준 32036번] 수열과 쿼리 45

Ohnim · 오님 2024. 7. 14. 21:17

문제 링크

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

 

문제를 바꿔서 생각하기

배열에 연산을 직접 하는것이 아니라 수학적인 방법으로 접근하면 조금 더 쉽게 문제를 해결할 수 있다.

 

1번 쿼리에서 주어지는 a, b를 아래와 같이 함수로 표현될 수 있다.(문제에서는 x, y라고 했는데, 좌표 평면에서의 x, y와 겹치기 때문에 헷갈리지 않기 위해 a, b로 바꿔서 적었다.)

$$f_i(x) = |x - a_i| + b_i$$

주어진 여러 개의 1번 쿼리를 통해 업데이트된 배열의 값은 각 1번 쿼리의 함수들을 더한 것으로 표현될 수 있다.

$$F(x) = \sum_{i=1}^{n} f_i(x) = \sum_{i=1}^{n}|x - a_i| + \sum_{i=1}^{n} b_i$$

2번 쿼리에서는 배열의 최솟값이 가장 처음 등장하는 지점과 그 값을 찾아야 한다. 배열 \(A\)를 함수 \(F(x)\)로 바꾸었기 때문에, 2번 쿼리는 함수 \(F(x)\)에서 최솟값을 찾는 문제로 변환할 수 있다.

 

함수에서 최솟값을 만드는 지점 찾기

함수 \(F(x)\)의 값이 \(x\)에 따라 어떻게 변하는지 알기 위해 x의 값이 변함에 따라 \(F(x)\)의 기울기가 어떻게 변하는지 생각해 보자. 함수 \(F(x)\)에 있는 \(a_i\)들을 작은 순서대로 \(a_1, a_2, \dots, a_n\)이라고 하자.

 

먼저, \(x\)가 \(a_1\)보다 작을 때 \(F(x)\)의 기울기는 음수이다. 즉, \(x\)가 커짐에 따라 \(F(x)\)의 값은 작아진다. \(x\)가 증가하면서 각 \(a_i\)를 만날 때마다 \(F(x)\)의 기울기는 조금씩 증가하다 \(x\)가 \(a_i\)들의 중앙값에 도달하는 순간 기울기는 0이 된다. 중앙값을 지나게 되면 \(F(x)\)의 기울기는 양수로 변하게 되며, \(x\)가 증가할수록 \(F(x)\)의 값은 커진다.

 

따라서 \(x\)가 \(a_i\)들의 중앙값일 때 \(F(x)\)의 값이 최소가 된다. \(a_i\)들의 개수가 짝수면 중앙값이 두 개가 되는데, 이때 \(F(x)\)의 값이 동일하므로 문제에서 요구한 대로 더 작은 값을 사용하면 된다.

 

함수의 최솟값 계산하기

\(F(x)\)의 최솟값과 그 때의 \(x\)를 출력하는 2번 쿼리를 계산하기 위해서는 \(a_i\)들의 중앙값을 찾고, \(F(x)\)를 계산하는 두 가지로 나눠서 생각할 수 있다.

 

변하는 수열에서 중앙값을 빠르게 찾기

\(F(x)\)에 존재하는 \(a_i\)들을 정렬한 뒤 중앙값을 찾을 수 있지만, 1번 쿼리가 들어올 때마다 \(a_i\)들의 순서가 바뀔 수 있어 정렬을 다시 해야 하기 때문에 효율적이지 못하다. 균형 잡힌 이진 탐색 트리를 직접 구현한다면 중앙값을 빠르게 찾을 수 있지만, 이는 구현에 공수가 많이 들기 때문에 제한된 시간 내에 문제를 풀어야 하는 알고리즘 대회에서는 적합하지 않다.

 

변하는 수열에서 중앙값을 빠르게 찾는 효율적인 방법 중 하나는 수열을 정렬한 뒤 절반은 최대 힙, 절반은 최소 힙으로 관리하는 것이다.

  1. 최대 힙의 크기는 최소 힙의 크기와 같거나 하나 더 크다.
  2. 최대 힙의 최댓값은 최소 힙의 최솟값보다 작거나 같다.

이 두 가지 원칙을 지키며 최대 힙과 최소 힙을 관리한다면, 변하는 수열에서 중앙값은 항상 최대 힙의 루트가 된다. 1번 쿼리가 들어왔을 때, 즉 수열에 새로운 값이 추가될 때에는 1번 원칙을 만족하게 최대 힙 또는 최소 힙에 수를 추가한 뒤 2번 원칙이 지켜지는지 확인하면 된다. 만약 2번 원칙이 지켜지지 않는다면 최대 힙과 최소 힙의 루트를 서로 바꿔준다.

priority_queue<long long, vector<long long>, less<long long>> maxHeap;
priority_queue<long long, vector<long long>, greater<long long>> minHeap;

void addElementToSequence(long long a) {
    if (maxHeap.size() == minHeap.size()) {
        maxHeap.push(a);
    } else {
        minHeap.push(a);
    }
    
    if (!maxHeap.empty() && !minHeap.empty() && maxHeap.top() > minHeap.top()) {
        long long rootOfMaxHeap = maxHeap.top();
        long long rootOfMinHeap = minHeap.top();
        
        maxHeap.pop();
        maxHeap.push(rootOfMinHeap);
        
        minHeap.pop();
        minHeap.push(rootOfMaxHeap);
    }
}

 

F(x) 계산하기

\(F(x)\)를 최소로 만드는 \(x\)를 찾았으니 실제로 \(F(x)\)를 계산할 차례이다. 여기서 \(x\)에 대입할 중앙값을 \(a_m\)이라고 하자. 중앙값 \(a_m\)을 기준으로 \(F(a_m)\)의 계산을 두 부분으로 나눌 수 있다.

  1. \(a_m\) 보다 작거나 같은 \(a_i\)들
  2. \(a_m\) 보다 큰 \(a_i\)들

\(a_m\) 보다 작거나 같은 원소들은 절댓값을 풀면 \(a_m - a_i\)이 된다. 이 값은 최대 힙의 원소 개수와 최대 힙의 원소들의 합을 이용하여 계산할 수 있다. \(a_m\) 보다 큰 원소들은 절댓값을 풀면 \(a_i - a_m\)이 된다. 이 값은 최소 힙의 원소 개수와 최소 힙의 원소들의 합을 이용하여 계산할 수 있다. 최대 힙과 최소 힙을 사용하여 중앙값을 관리할 때, 각 힙의 합을 계산하면 매번 모든 원소들의 합을 계산하지 않아도 된다.

 

\(\sum_{i=1}^{n} b_i\)는 이제까지 1번 쿼리로 들어온 b의 값들을 합이므로 별도 변수로 저장하여 관리한다.

 

이렇게 하면 2번 쿼리를 \(O(1)\)에 계산할 수 있다.

 

소스코드

더보기
더보기 
#include <stdio.h>
#include <queue>
#include <algorithm>

using namespace std;

priority_queue<long long, vector<long long>, less<long long>> maxHeap;
priority_queue<long long, vector<long long>, greater<long long>> minHeap;
int q, t;
long long sumOfMaxHeap, sumOfMinHeap, sumOfB;

void addElementToSequence(long long a) {
    if (maxHeap.size() == minHeap.size()) {
        maxHeap.push(a);
        sumOfMaxHeap += a;
    } else {
        minHeap.push(a);
        sumOfMinHeap += a;
    }
    
    if (!maxHeap.empty() && !minHeap.empty() && maxHeap.top() > minHeap.top()) {
        long long rootOfMaxHeap = maxHeap.top();
        long long rootOfMinHeap = minHeap.top();
        
        maxHeap.pop();
        maxHeap.push(rootOfMinHeap);
        sumOfMaxHeap = sumOfMaxHeap - rootOfMaxHeap + rootOfMinHeap;
        
        minHeap.pop();
        minHeap.push(rootOfMaxHeap);
        sumOfMinHeap = sumOfMinHeap - rootOfMinHeap + rootOfMaxHeap;
    }
}

int main() {
    scanf("%d", &q);
    
    while (q--) {
        scanf("%d", &t);
        
        if (t == 1) {
            long long a, b;
            scanf("%lld%lld", &a, &b);
            
            sumOfB += b;
            addElementToSequence(a);
        } else {
            long long minXValue = maxHeap.top();
            long long minYValue = (minXValue * (long long)maxHeap.size() - sumOfMaxHeap) + (sumOfMinHeap - minXValue * (long long)minHeap.size()) + sumOfB;
            
            printf("%lld %lld\n", minXValue, minYValue);
        }
    }
}
저작자표시 비영리 변경금지