BOJ 1168 - 요세푸스 문제 2

• 저번 문제에서 n, k의 범위가 10^5로 넓어진 문제이다. (풀고 걱정했던 내용이 바로 나왔다.)

문제 풀이

• segment tree의 leaf노드를 n명의 사람이라 하고 제거되지 않으면 1, 제거된 상태를 0이라 정의했다. 이후 저번 문제와 똑같은 방법으로 풀었다.

• [0, e]의 구간합이 k인 e를 구할 때 처음에는 parametric search를 이용하려했는데 7469번을 풀 때 segment tree 탐색하던 것이 생각나 그걸 사용했다. 저 구간을 구해도 끝에 0이 몇 개 붙는 경우가 존재하기 때문에 findlast1을 이용해서 저 구간의 leaf노드 중 값이 1인 마지막 leaf를 찾았다.

소스코드

#include<cstdio>
#include<vector>
#include<tuple>
using namespace std;
typedef vector<int> vi;
typedef tuple<int, int, int> ti;

int mid(int s, int e){return (s+e)>>1;}
int init(vi& num, vi& st, int tidx, int s, int e);
int query1(vi& st, int tidx, int s, int e, int fl, int fr);//return partial sum
ti query2(vi& st, int tidx, int s, int e, int val);//return index of e, sum(0, e)==val
int findlast1(vi& st, int n, int tidx, int s, int e);
void update(vi& st, int tidx, int s, int e, int nidx, int diff);

int main()
{
	int n, k, curk, curp, sz=1;
	scanf("%d %d", &n, &k);
	for(;sz<n;sz*=2);
	vi st(2*sz), num(n, 1), sol;
	init(num, st, 1, 0, n-1);
	curp=-1;
	for(int i=n;i>0;i--){
		int idx, s, e, aftercurp, curk;
		if(curp==n-1) aftercurp=0;
		else aftercurp=query1(st, 1, 0, n-1, curp+1, n-1);
		if(aftercurp>=k) curk=(k+i-aftercurp)%i;
		else curk=(k-aftercurp)%i;
		if(curk==0) curk=i;
		tie(idx, s, e)=query2(st, 1, 0, n-1, curk);
		curp=findlast1(st, n, idx, s, e);
		sol.push_back(curp+1);
		update(st, 1, 0, n-1, curp, -1);
	}
	printf("<");
	for(int i=0;i<sol.size()-1;i++) printf("%d, ", sol[i]);
	printf("%d>", sol.back());
}

int init(vi& num, vi& st, int tidx, int s, int e){
	if(s==e) return st[tidx]=num[s];
	return st[tidx]=init(num, st, tidx*2, s, mid(s, e))+init(num, st, tidx*2+1, mid(s, e)+1, e);
}

int query1(vi& st, int tidx, int s, int e, int fl, int fr){
	if(s>fr || e<fl) return 0;
	if(s>=fl && e<=fr) return st[tidx];
	return query1(st, tidx*2, s, mid(s, e), fl, fr)+query1(st, tidx*2+1, mid(s, e)+1, e, fl, fr);
}

ti query2(vi& st, int tidx, int s, int e, int val){
	if(st[tidx]==val) return make_tuple(tidx, s, e);
	if(val>st[tidx*2]) return query2(st, tidx*2+1, mid(s, e)+1, e, val-st[tidx*2]);
	return query2(st, tidx*2, s, mid(s, e), val);
}

int findlast1(vi& st, int n, int tidx, int s, int e){
	if(s==e) return s;
	if(st[tidx*2+1]==0) return findlast1(st, n, tidx*2, s, mid(s, e));
	return findlast1(st, n, tidx*2+1, mid(s, e)+1, e);
}

void update(vi& st, int tidx, int s, int e, int nidx, int diff){
	if(s>nidx || e<nidx) return;
	st[tidx]+=diff;
	if(s!=e){
		update(st, tidx*2, s, mid(s, e), nidx, diff);
		update(st, tidx*2+1, mid(s, e)+1, e, nidx, diff);
	}
}

풀고나서

• 처음에는 segment tree의 쿼리가 O(logN)이기 때문에 O(N^2logN)으로 안될 것 같았는데 구간합이 curk인 구간 탐색을 logN만에 구현해서 O(NlogN)으로 풀었다. 위에 7469번에서 이 내용도 구현했었는데 까먹었다… 저번 문제를 풀고 나서 고민했던 STL과 비슷한 게 segment tree인 것 같다.

• tuple을 한 번 사용해보았다.

• 아무리 생각해도 실버3난이도의 문제는 아닌거가튼뒈

---

(2020.11.12)

• 내 질문 떄문에 시간제한이 바뀌었고 그 결과 난이도도 다시 책정되었다. 이제 플레티넘 5 난이도의 문제로 바뀌었다!!

---