백준 2517번 - 달리기

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

2517번: 달리기

 

문제 분석

 

문제 내용 자체는 간단하다.

 

A의 등수는 A보다 앞에 있는 사람 중 A보다 달리기 평소 실력이 낮은 친구가 몇 명인지를 알아야 구할 수 있다.

 

가장 간단한 방법은 당연히 브루트포스이다.

각 인원마다 자신보다 앞에 있는 사람들의 평소 실력을 비교해보면 된다.

이때 문제의 N제한이 50만이기 때문에 당연히 1+2+3+...+50만 = O(50만*50만+1/2) = O(천억...?) 이 나온다.

 

천억이라... 

1초에 1억 번 연산이면 1000초 = 약 16분 정도겠네

 

어쨌든 이 방법은 아닌걸 당연히 알았을 것이다.

 

그럼 어떤 방법이 좋을까?

만약 i번째 등수의 사람의 평소 능력이 x라 할 때 1 ~ i - 1번째 사람 중 평소 능력이 x보다 작은 값을 구하면 된다.

이때 배열 A[index] 에는 평소 실력이 index인 사람의 수가 저장되어 있다고 생각해보자.

만약 1 ~ i - 1번째 사람까지 순서대로 자신의 평소 능력을 차곡차곡 A[index]에 저장했다고 생각해보자.

(예를 들어 1번째 사람의 평소 능력이 2이면 A[2] += 1 이란 말임)

그럼 i번째 사람의 평소 능력이 x라 했으므로 A[1] + A[2] + ... + A[X-1]이 i번째 사람보다 앞에 있는 사람 중 자신보다 평소 실력이 낮은 사람의 수이다.

 

(위의 내용이 이해가 어렵다면 예를 들어 설명해보자.

 

다음과 같은 경우가 주어졌다고 가정해보자.

 

2 5 7

 

그럼 첫 번째 사람은 A[2] += 1을 하게 된다.

두 번째 사람은 A[1]+A[2]+A[3]+A[4]의 값이 자신보다 앞에 있는 사람 중 자신보다 평소 실력이 낮은 사람의 수이다.

따라서 1이 될 것이고 A[5] += 1을 하게 된다.

마지막으로 세 번째 사람은 A[1]+A[2]+...+A[6]의 값이 자신보다 앞에 있는 사람 중 자신보다 평소 실력이 낮은 사람의 수이다.

따라서 2가 될 것이고 A[7] += 1을 하게 된다.

 

어렵지 않다. 그쵸?)

 

음... 저 형태 어디서 많이 봤는데?

맞다. PrefixSum이다. 

이때 N제한이 50만이기 때문에 일반적인 PrefixSum으로 구할 수 없다.

하지만 우리는 BIT, 세그먼트 트리를 알고 있지 않은가?

모르면 아래에 내용을 참고하면 된다^^

https://kimtaehyun98.tistory.com/112

Binary Index Tree(BIT, Fenwick Tree)

  

그럼 저 값이 그대로 답이 되는 것일까?

당연히 아니다.

결국 자신의 현재 위치가 주어지기 때문에 이 값과 비교해야 한다.

 

따라서 최대로 가능한 등수 = 현재 등수 - 자신보다 앞에 있는 사람 중 자신보다 평소 실력이 낮은 사람이다.

 

나는 문제를 보면서 가장 고민했던 부분이 N 제한이 50만 인 것보다 각 능력이 최대 10억이란 것이었다.

 

BIT든 세그먼트 트리든 알고리즘을 사용하려 해도 결국 Tree는 배열로 만들어지기 때문에 배열의 크기는 10억을 넘을 수 없었다.

 

가장 먼저 떠오른 방법은 배열을 여러 개로 나누는 방법이었다.

하지만 결국 그렇게 되면 가능이야 하겠지만 프로그램 전체의 메모리에서는 변함이 없기 때문에 다른 방법을 찾아야 했다.

 

그래서 생각해낸 것이 "입력된 수를 정렬 후 순서대로 수치 설정"이었다.

결국 이 문제가 플래 4인 이유는 위의 문장 하나 때문이다.

문제의 해법은 사실 골드 1 BIT 문제나 다를 바가 없었다.

 

이 방법이 가능한 이유는 사실문제에 쓰여있었다.

"단, 참가한 선수들의 평소 실력은 모두 다르다."

항상 "단, " 이란 말이 붙으면 뭔가 꿍꿍이가 있겠구나 하고 주의 깊게 살펴본다.

 

이제 BIT도 구현이 가능해졌고 그렇다면 PrefixSum도 구할 수 있다.

 

위의 과정을 정리해보면 최종적인 풀이과정은 다음과 같다.

 

1. 입력
2. 입력받은 숫자를 정렬 후 수치 재 설정 (1~50만 사이로)
3. 순서대로 PrefixSum을 구하여 현재 등수 - PrefixSum을 하여 정답을 출력한다.
4. BIT에 자신의 정보를 추가한다.
5. 3,4번 과정을 n번 반복한다.

 

코드는 아래와 같다. (주석 열심히 달았어요)

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

int tree[500005];
int n, x;
vector<pii>info;

int sum(int i) {
    int ans = 0;
    while (i > 0) {
        ans += tree[i];
        i -= (i & -i);
    }
    return ans;
}

void update(int i, int num) {
    while (i <= n) {
        tree[i] += num;
        i += (i & -i);
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        info.push_back(pii(x, i + 1)); // 평소 실력, index
    }
    sort(info.begin(), info.end());
    for (int i = 0; i < n; i++) {
        info[i].first = i + 1; // 1~10억 사이의 숫자를 1~50만으로 바꿔줌
        swap(info[i].first, info[i].second); // 다시 index순으로 정렬해주기 위해서
    }
    sort(info.begin(), info.end()); // 다시 index 순으로 정렬
    memset(tree, 0, sizeof(tree));
    for (int i = 0; i < n; i++) {
        // 출력해야 하는 값 = 현재 등수 - 앞에 있는 사람 중 나보다 평소 실력이 낮은 사람들
        int temp = info[i].second;
        // 자신보다 달리기가 느린 친구들이 몇명이나 있는지 확인 후 출력
        cout << (i + 1) - sum(temp - 1) << "\n";
        // 자신의 정보 bit에 update
        update(temp, 1);
    }
}

 

BIT 코드가 워낙 짧기 때문에 세그먼트 트리 대신 사용해보았다.

세그먼트 트리로 구해도 결국 똑같은 과정이다. Sum과 update 함수의 코드만 다를 뿐..