백준 2517번 달리기

< 백준 2517번 달리기 - 마포 코딩박 >

사용한 알고리즘: Fenwick tree


 선수들이 현재 달리고 있는 순서 대로, 선수들의 능력치가 주어집니다. 능력이 큰 선수는 자신보다 앞에 있는 능력이 작은 선수를 앞지를 가능성이 있습니다. 이때 각 선수의 가능한 최대 등수를 구하는 문제였습니다.
 사실 " 각 선수의 가능한 최대 등수 = 들어온 순서 - 자신 앞에 있는 능력 작은 선수 수 " 입니다.

문제풀이는 다음과 같습니다.
(1) (코드: 12~16, 51~59)
 선수의 능력이 1~10^9 이므로 이를 그대로 배열로 받을 수 없습니다. ( 터집니다.... )
 하지만 선수의 수가 3~5*10^5 밖에 안되므로, 선수들의 능력치를 최대 5*10^5 로 압축했습니다. 즉 선수 능력치가 극단적으로 10, 222222, 99999999999 인 경우나 1, 2, 3 인 경우나 대소는 같습니다.
 따라서 저는 능력이 큰 순으로 정렬을 시켜, 가장 큰 값을 5*10^5 부터 차례로 바꾸어 주며 능력을 압축했습니다. ( 선수 수가 최대 5*10^5 입니다. )

(2) (코드: 17~39, 60~68)
 들어온 순으로 다시 정렬 시켰습니다. 이후 빨리 들어온 선수부터 보면서 등수를 매겼습니다.
 i 번째 선수의 가능한 최대 등수는 i - ( 자신 앞 작은 능력 선수 수 ) 입니다.
 i 번째 선수앞에 있는 자신보다 작은 능력의 선수 수를 fenwick tree 로 계산해주었습니다.

	#include <iostream>
	#include <utility>
	#include <vector>
	#include <algorithm>
	using namespace std;
	// 키를 압축해서 , Fenwick tree ~~
	// 들어온 순서, 실력
	typedef pair<int, int> pii;
	const int MAX = 500000;
	int N;
	vector<pii> V;
	// 실력 높은순
	bool cmp1(const pii &a, const pii &b){
	return a.second > b.second;
	}
	// 빨리 들어온 순
	bool cmp2(const pii &a, const pii &b){
	return a.first < b.first;
	}
	// Fenwick tree
	int tree[MAX+1];
	int Li(int x){
	return x&(-x);
	}
	int sum(int x){
	int ret = 0;
	while(x>0){
	ret += tree[x];
	x-=Li(x);
	}
	return ret;
	}
	void update(int x){
	while(x<=MAX){
	tree[x]++;
	x+=Li(x);
	}
	}
	int main(){ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	#endif
	cin >> N;
	for (int i = 1; i <= N; ++i){
	int ability;
	cin >> ability;
	V.push_back(pii(i,ability));
	}
	// 능력 큰순으로 정렬
	sort(V.begin(),V.end(),cmp1);
	// N이 최대 500000 이므로 능력을 압축해준다.
	// 예를들어 능력이 각각 100 15 1 인 거나 3 2 1 이나 대소는 똑같다.
	int Abil = MAX+1;
	for (int i = 0; i < N; ++i){
	V[i].second = Abil;
	Abil--;
	}
	sort(V.begin(),V.end(),cmp2);
	// 들어온 순서대로 보면서, 이전에 자신보다 능력이 낮은 사람이 몇명 왔나 센다.
	// 등수 = 들어온 순서 - 자신보다 낮은 능력 사람 수
	for(auto now: V){
	// now.second : now.first 번째 사람의 능력치
	cout << now.first- sum(now.second) << '\n';
	update(now.second);
	}
	return 0;
	}

view raw BOJ 2517.cpp hosted with ❤ by GitHub