티스토리 뷰

조세퍼스 문제 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))\)에 해결할 수 있다.


소스 코드


댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함