백준 14449 c++ "Balanced Photo" -PlusUltraCode-

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

 

[필자 사고]

이 문제는 inverstion Counting 을 응용한 문제이다.

현재 idx보다 앞 뒤로 놓여진 숫자들을 구해야 된다.

필자는 세그먼트 트리를 이용하였다. 

 

이 문제에서 핵심은 좌표 압축이라고 생각한다.

기존 배열을 idx와 val 를 함께 저장하고 val를 기준으로 오름차순을 진행한다.

진행한 뒤 compressedArr[arr[i].second] = i 를 하게 되고 사용할때는 compressedArr[i]를 사용하면

좌표 압축 성공이다.

[코드 해설]

1. 입력 처리 및 초기화

사용자로부터 배열 크기 NNN과 NNN개의 숫자를 입력받는다. 입력받은 숫자들을 값과 인덱스로 묶어서 저장한 뒤, 값을 기준으로 정렬한다. 정렬된 배열을 기반으로 각 숫자에 대해 압축 좌표값(1부터 시작하는 새로운 인덱스)을 생성한다. 이렇게 생성된 압축 좌표는 세그먼트 트리에서 사용할 작은 범위의 값으로 변환된다.

---

2. 세그먼트 트리 업데이트

세그먼트 트리는 특정 인덱스의 값을 업데이트하는 함수가 있다. 이 함수는 범위의 중간값을 기준으로 좌측이나 우측으로 분할하여 재귀적으로 호출된다. 최종적으로 리프 노드에 도달하면 값을 갱신하고, 해당 값을 기반으로 부모 노드들을 갱신한다.

---

3. 세그먼트 트리 구간 합 계산

세그먼트 트리를 이용해 특정 구간에 포함된 값의 합을 계산하는 함수가 있다. 이 함수는 주어진 구간이 세그먼트 트리의 현재 범위와 겹치는지 확인하고, 완전히 포함되면 해당 노드의 값을 반환한다. 그렇지 않으면 좌우 자식을 재귀적으로 호출하여 합산한다.

---

4. 게임 시작 로직

• 첫 번째 단계: 배열을 왼쪽에서 오른쪽으로 탐색하며, 현재 숫자 이후에 위치한 더 큰 숫자의 개수를 세그먼트 트리를 통해 계산한다. 이 값을 저장한 후, 현재 숫자를 세그먼트 트리에 추가한다.
• 두 번째 단계: 세그먼트 트리를 초기화한 뒤, 배열을 오른쪽에서 왼쪽으로 탐색하며, 현재 숫자 이전에 위치한 더 큰 숫자의 개수를 계산하고 저장한다. 이후 현재 숫자를 세그먼트 트리에 추가한다.

---

5. 조건 확인 및 결과 계산

각 숫자에 대해, 그 이후의 더 큰 숫자 개수와 그 이전의 더 큰 숫자 개수를 비교한다. 이 두 값 중 최소값과 최대값을 계산하고, 최대값이 최소값의 두 배보다 큰 경우를 카운트한다. 최종적으로 이러한 숫자의 개수를 출력한다.

[소스 코드]

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

int N;
vector<pair<ll, int>> arr;
vector<ll> compressedArr;
vector<ll> tree;

void Input() {
    cin >> N;
    tree.resize(4 * N + 1);
    arr.resize(N + 1);
    compressedArr.resize(N + 1);

    for (int i = 1; i <= N; i++) {
        ll num;
        cin >> num;
        arr[i] = { num, i };
    }

    sort(arr.begin() + 1, arr.end());
    for (int i = 1; i <= N; i++) {
        compressedArr[arr[i].second] = i;
    }
}

void Update(int node, int start, int end, int idx, int diff) {
    if (start == end) {
        tree[node] += diff;
        return;
    }

    int mid = (start + end) / 2;
    if (idx <= mid) {
        Update(node * 2, start, mid, idx, diff);
    }
    else {
        Update(node * 2 + 1, mid + 1, end, idx, diff);
    }

    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

ll Query(int node, int start, int end, int left, int right) {
    if (end < left || right < start) return 0;
    if (left <= start && end <= right) return tree[node];

    int mid = (start + end) / 2;
    return Query(node * 2, start, mid, left, right) +
        Query(node * 2 + 1, mid + 1, end, left, right);
}

void Game_Start() {
    vector<ll> countFirst(N + 1);
    vector<ll> countSecond(N + 1);

    for (int i = 1; i <= N; i++) {
        int idx = compressedArr[i];
        countFirst[i] = Query(1, 1, N, idx + 1, N);
        Update(1, 1, N, idx, 1);
    }

    fill(tree.begin(), tree.end(), 0); // Reset the segment tree

    for (int i = N; i >= 1; i--) {
        int idx = compressedArr[i];
        countSecond[i] = Query(1, 1, N, idx + 1, N);
        Update(1, 1, N, idx, 1);
    }

    ll count = 0;
    for (int i = 1; i <= N; i++) {
        ll firstNum = countFirst[i];
        ll secondNum = countSecond[i];

        ll minNum = min(firstNum, secondNum);
        ll maxNum = max(firstNum, secondNum);
        if (maxNum > 2 * minNum) {
            count++;
        }
    }

    cout << count;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    Input();
    Game_Start();
}