[BOJ 12016 // C++] 라운드 로빈 스케줄러

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 12016번 문제인 라운드 로빈 스케줄러이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/12016

12016번: 라운드 로빈 스케줄러

라운드 로빈 스케줄링(round-robin scheduling)에 대해서는 다음 링크를 참고하자:

en.wikipedia.org/wiki/Round-robin_scheduling

라운드 로빈 스케줄링은 위의 링크와 같이 작동하지만, 이 문제에서 위 라운드 로빈 알고리즘과 동일하게 진행하면서 값을 찾는 것은 매우 비효율적이다. 따라서 이 문제를 풀기 위해서는 다른 방법이 필요하다.

 

글쓴이는 이 문제를 풀기 위해 n개의 원소의 구간 최솟값을 반환할 수 있는 세그먼트 트리(segment tree)를 구현하고, 최솟값을 하나 읽을 때마다 입력으로 주어질 수 없는 큰 수(1000000001)로 해당 최솟값을 갱신하는 방법을 선택했다. 또한, 그때그때 범위에 남아있는 수를 알아야 출력할 값을 계산해낼 수 있으므로, n개의 리프 노드의 값이 1이고 구간 합을 반환하는 세그먼트 트리를 같이 구현하였다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <cmath>
using std::cin; using std::cout;
using std::min;
typedef long long ll;

ll arr[100001];
int segtree[262145]; // 전체의 최솟값을 얻을 segtree
int cnttree[262145]; // 구간의 남은 원소개수를 셀 cnttree
int minindex;

int initsegtree(int L, int R, int sIdx) { // segtree의 초기화
	if (L == R) segtree[sIdx] = arr[L];
	else segtree[sIdx] = min(initsegtree(L, (L + R) / 2, sIdx * 2), initsegtree((L + R) / 2 + 1, R, sIdx * 2 + 1));
	return segtree[sIdx];
}

int segupdate(int L, int R, int sIdx, int minvalue) {
	if (L == R) {
		segtree[sIdx] = 1000000001;
		minindex = L; //업데이트하며 계산에 필요한 minindex값을 저장
	}
	else if (segtree[sIdx * 2] == minvalue) {
		segtree[sIdx] = min(segupdate(L, (L + R) / 2, sIdx * 2, minvalue), segtree[sIdx * 2 + 1]);
	}
	else segtree[sIdx] = min(segtree[sIdx * 2], segupdate((L + R) / 2 + 1, R, sIdx * 2 + 1, minvalue));
	return segtree[sIdx];
}

int initcnttree(int L, int R, int sIdx) { // cnttree의 초기화
	if (L == R) cnttree[sIdx] = 1;
	else cnttree[sIdx] = initcnttree(L, (L + R) / 2, sIdx * 2) + initcnttree((L + R) / 2 + 1, R, sIdx * 2 + 1);
	return cnttree[sIdx];
}

ll cntrq(int L, int R, int qL, int qR, int sIdx) { // L부터 R까지 현재 남아있는 숫자의 개수를 반환하는 쿼리
	if (qL <= L && R <= qR) return cnttree[sIdx];
	if (qR < L || R < qL) return 0;
	return cntrq(L, (L + R) / 2, qL, qR, sIdx * 2) + cntrq((L + R) / 2 + 1, R, qL, qR, sIdx * 2 + 1);
}

void cntupdate(int L, int R, int qIdx, int sIdx) { // 개수 업데이트: 1개 있던 것이 0개가 되는 것이므로 1씩 빼주는 것으로 충분
	if (R < qIdx || qIdx < L) return;
	cnttree[sIdx]--;
	if (L != R) {
		cntupdate(L, (L + R) / 2, qIdx, sIdx * 2);
		cntupdate((L + R) / 2 + 1, R, qIdx, sIdx * 2 + 1);
	}
}

int main() {
	std::ios::sync_with_stdio(0);
	cin.tie(0);

	int N; cin >> N;
	for (int i = 1;i <= N;i++) {
		int x; cin >> x; arr[i] = x;
	}
	initsegtree(1, N, 1); initcnttree(1, N, 1); //초기화
	ll ans = 0;
	ll oldindex = 0;
	ll oldminvalue = 1;
	for (int i = N;i > 0;i--) {
		ll minvalue = segtree[1];
		segupdate(1, N, 1, minvalue);
		if (oldindex < minindex) {
			ans += cntrq(1, N, oldindex + 1, minindex, 1) + (minvalue - oldminvalue) * i;
		}
		else ans += cntrq(1, N, oldindex + 1, N, 1) + cntrq(1, N, 1, minindex, 1) + (minvalue-oldminvalue-1)*i;
		arr[minindex] = ans;
		cntupdate(1, N, minindex, 1);
		oldindex = minindex;
		oldminvalue = minvalue;
	}
	for (int i = 1;i <= N;i++) cout << arr[i] << '\n';
	return 0;
}