boj, 백준) 2517. 달리기 (C++)

1. 문제 링크

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

2517번: 달리기

2. 문제 개요

요약하자면, 평소 실력이 정수로 주어진다. 반환점을 돌고 일렬로 선 상태에서, 실력이 앞서 있는 사람보다 높다면 앞질러 도착할 수 있다. 이때 최선의 등수를 계산하는 프로그램을 작성하시오.

 

3. 문제 힌트

N이 최대 50만이기 때문에, O(n^2)을 사용하면 안 됨.

O(nlogn)으로 구할 수 있는 경우를 찾아보자.

즉, 모든 숫자에 대해서 탐색을 해야 하므로 1번의 연산은 O(logn)이어야 한다는 점.

 

세그먼트 트리를 만들 때,

리프 노드의 값들은 능력으로 하고 그 능력이 x이라고 할 때,

세그먼트 트리 (0, x] 범위를 탐색하고 앞서 있는 사람들이 몇 명인지 log n의 시간으로 세어보자.

 

그리고 리프 노드 값을 능력으로 한다고 했는데 능력은 최대 10억이다. 배열 10억 개 만들면 안 되니까 좌표를 압축해줘야 한다. N이 50만까지이므로 (0,500000)의 범위로 압축시키자.

ex) 10000000,4,2,5라고 한다면, 0,2,1,3과 같은 방식으로.

 

 

4. 문제 풀이

 

여기서 세그먼트 트리를 만들 때 바로 초기화를 하지 않는다.

리프 노드의 개수가 n개일 때 트리의 높이는 0부터 시작한다 가정하면, log2(n)을 올림 한 것이다.

높이는 저렇고, 전체 노드의 개수는 2^(h+1)-1이 되어야 할 것이다. 

하지만 세그먼트의 트리 인덱스는 1부터 시작하므로 2^(h+1) 개로 초기화해주었다.

여기까지 세그먼트 트리의 공간을 만들어 주는 것이고,

 

이제 메인 알고리즘으로 들어가 본다면

뭐, 알고리즘 자체는 모든 분들이 쉽다고 생각했을 겁니다. 왜냐하면 이게 log(n)으로 푸는 게 어려워서 그렇지 개념 자체는

어떤 i번째 사람 중에서 본인보다 앞에 있는, 즉, (0, i) or (0, i] 구간의 사람들 중 자신보다 능력이 높은 사람의 수 +1 = 본인의 최선의 등수이고 이것은 캐치하는데 그렇게 어렵지 않을 것이다.

 

코드의 Query함수는 가장 일반적인 부분합을 구하는 함수이다. 범위를 주고 그 범위의 부분합을 구한다.

Update함수는 Segment에 사람을 삽입한다고 생각하면 될 것 같다.

 

처음에 사람들의 능력을 입력받을 때, 몇 번째인지(인덱스)도 함께 넣을 것이다. 왜냐하면 좌표 압축을 하기 위함이다.

좌표압축을 하기 위해, 각 사람의 능력치를 내림차순으로 정렬할 것이다.

그리고 정렬한 순서대로 능력치를 0~n-1로 대입을 해준다. 그렇게 되면 능력이 가장 높은 사람의 숫자가 가장 작아지는 결과를 얻을 수 있다. 따라서 본인의 앞쪽에 낮은 숫자가 있다면 앞서갈 수 없다는 의미를 갖는다. 이렇게 압축한 능력을 상대적인 능력이라고 하자.

그다음 원래대로 돌리기 위해 몇 번째인지, 인덱스를 기준으로 다시 정렬해주자.

 

그다음 방금 앞에서 말했던 알고리즘을 생각해보자, 앞에 있는 사람 순서대로 자신의 상대적인 능력에 맞춰서 세그먼트 트리에 삽입될 것이다. 능력이 5라면 5번에 맞게 세그먼트 트리에 삽입이 될 것이다.

상대적인 능력을 x라고 하고 (0, x] 범위의 부분합을 구하자, 첫 번째 사람이니 0이 될 것이고, 자신의 앞에 0명이 있다는 소리이므로 +1을 해서 출력을 해준다. 그리고 본인의 위치에 +1을 해주고 세그먼트 트리를 수정하자.

 

다음, 상대 능력이 x+1인 사람이 있다. 앞서 삽입한 x보다 상대적인 능력이 높지만(우선순위는 낮음) 앞서 정의한 것에 따라 자기보다 상대 능력이 낮은 사람은 앞서 갈 수 없다. 따라서 부분합을 구하면 1이 되고, 1+1 해서 최대 2등을 할 수 있게 된다.

 

이런 과정을 반복하면 된다.

 

 

 

5. 코드

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

vector<pair<int, int>> v;
int n;

bool comp_ability(pair<int, int> a, pair<int, int> b)
{
	return a.second > b.second;
}
bool comp_index(pair<int, int> a, pair<int, int> b)
{
	return a.first < b.first;
}

class Segment_tree
{
	public:
		Segment_tree() {}
		Segment_tree(int tree_size) { tree.resize(tree_size); }// 1부터 시작


		int query(int cur, int start, int end, int left, int right)
		{
			if (end < left || right < start)
				return 0;

			if (left <= start && end <= right)
				return tree[cur];

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

		//범위가 아님
		int update(int cur, int start, int end, int target, int val)
		{
			if (target < start || end < target)
				return tree[cur];

			if (start == end)
			{
				tree[cur] += val;
				return tree[cur];
			}
			int mid = (start + end) / 2;
			return tree[cur] = update(cur * 2, start, mid, target, val) + update(cur * 2 + 1, mid + 1, end, target, val);

		}
		vector<int> tree;
};

int main()
{
	scanf("%d", &n);
	v.resize(n);
	for (int i = 0; i < n; ++i){
		v[i].first = i;
		scanf("%d", &v[i].second);
	}
	sort(v.begin(), v.end(), comp_ability);

	//좌표 압축
	for (int i = 0; i < n; ++i) 
		v[i].second = i;
	
	sort(v.begin(), v.end(), comp_index);

	int h = (int)ceil(log2(n));
	int tree_size = 1 << (h + 1);
	Segment_tree sgt(tree_size);

	for (int i = 0; i < n; ++i) {
		int frontnum = 0;
		frontnum = sgt.query(1, 0, n - 1, 0, v[i].second);
		printf("%d\n", frontnum + 1);
		sgt.update(1, 0, n - 1, v[i].second, 1);
	}

	return 0;
}

 

6. 실행 결과

 

지적 댓글 환영입니다~