[BOJ] 백준 1168번: 조세퍼스 문제 2

조세퍼스 문제 2

문제

조세퍼스 순열을 구하시오! (1 ≤ M ≤ N ≤ 100,000)

문제 풀이

naive 하게 \(O(NM)\)에 풀 수 있다. \(sum[i]=\sum_1^i{alive[x]},\:(alive[i]=i번째 \:사람이 \:살아있으면 \:1 \:아니면 \:0)\)  라고 정의 하자. 현재 i번째 사람부터 시작한다면 제거된 사람을 제외하고 \(sum[j]-sum[i]=m\)을 만족하는 j값을 찾으면 된다. m값이 현재 남아있는 사람보다 큰 경우와 j인덱스가 한 바퀴를 돌아 i보다 작은 경우 두 경우만 처리를 해주고 찾게 되면 여전히 \(O(NM)\)이다. 하지만 \(sum[i]\)는 순 증가함수고 근이 한 개만 존재하기 때문에 parametric search를 사용할 수 있고 j값을 \(O(log2{N})\)에 찾을 수 있다.

각각 사람이 제거된 경우 업데이트와 구간 질문을 \(O(log2{N})\)에 해주는 세그먼트 트리나 팬윅트리를 이용하여 \(sum[i]\)를 관리하면 된다. \(N\)명을 제거하기 때문에 \(O(Nlog2{N})\) 로 해결할 수 있다.

다른 방법으로는 sqrt decomposition을 이용해 \(O(N\sqrt(N))\)에 해결할 수 있다.

소스 코드

#include <bits/stdc++.h> using namespace std; int tree[100001]; void update(int idx, int val){ while(idx<=100000){ tree[idx]+=val; idx+=idx&(-idx); } } int query(int idx){ int ret=0; while(idx>0){ ret+=tree[idx]; idx-=idx&(-idx); } return ret; } int n, m; bool possi(int x, int st, int k, int cnt){ if(x>st) return query(x)-query(st)>=k; return cnt-query(st)+query(x)>=k; } int main(){ scanf("%d%d", &n, &m); for(int i=1;i<=n;i++) update(i, 1); int now=0; printf("<"); while(true){ int cnt=query(n); int k=(m-1)%cnt+1; int le, ri, mid; le=1;ri=n; int next; while(le<=ri){ mid=(le+ri)/2; int xmid=(now+mid-1)%n+1; if(possi(xmid, now, k, cnt)){ next=xmid; ri=mid-1; } else le=mid+1; } printf("%d", next); update(next, -1); now=next; if(cnt>1) printf(", "); else break; } printf(">\n"); return 0; }  

#include <bits/stdc++.h> using namespace std; int cnt[100005]; int sq[1000]; int sz; int n, m; int main(){ scanf("%d%d", &n, &m); sz=sqrt(n); for(int i=1;i<=n;i++){ cnt[i]++; sq[i/sz]++; } int now=0; printf("<"); int count=n; while(true){ int k=(m-1)%count+1; int block=now/sz; int sum=0; int next; if(now%sz!=0){ block++; for(next=now;next<=n&&next/sz<block;next++) if(sum+cnt[next]>=k) goto n; else sum+=cnt[next]; } for(;block<=n/sz;block++){ if(sum+sq[block]>=k) break; else sum+=sq[block]; } if(block>n/sz){ for(block=0;;block++){ if(sum+sq[block]>=k) break; else sum+=sq[block]; } } for(next=block*sz;next<=n;next++){ if(sum+cnt[next]>=k) break; else sum+=cnt[next]; } n:; printf("%d", next); cnt[next]--; sq[next/sz]--; now=next; if(count>1) printf(", "); else break; count--; } printf(">\n"); return 0; }