BOJ 1168 조세퍼스 문제2

이 문제는 n제한이 10만이기 때문에 Fenwick Tree를 이용해서 풀어야한다고 들었는데, 모르겠어서 인터넷을 뒤지다보니 참고할만한 링크를 발견했다.
http://blog.sisobus.com/search/label/BOJ#.V84smK2vYqM
http://xoding.tistory.com/27

일단 핵심은
Fenwick Tree를 이용해서 한 사람의 앞 뒤로 몇명이 있는지 알 수 있다는 것과
거기에 binary search를 이용해서 해당하는 사람을 빠르게 찾을 수 있다는 것이다.

어느정도 이해를 한 후 내가 직접 구현해보려고 했는데, binary search를 구현할 때, left, right를 설정하기가 좀 힘들었다. 이게 원형으로 계속 돌기 때문에 원하는 index를 얻기 위해서는 나머지 연산을 해줘야하고, left, right는 나머지 연산을 하면 안되고...음 짜기도 전에 생각부터가 복잡해서 그냥 그만뒀다.

저 위에 링크에서 sisobus님의 코드가 매우 간결하고 깔끔해서 봤는데, binary search를 그냥 1~n까지 하는 것 같아보인다. 어떻게 매번 이렇게 하는 건지 이해가 잘 안돼서 내 방식대로 하려다가 더 어려워서 다시 생각해보니 어느정도 이해가 됐다. 정말 깔끔하고 멋진 것 같다.

매번 1~n에서 binary search를 하기위해서는 시작(1)에서 얼마나 떨어져있는 사람이 다음 차례인지만 알면 된다. 그 부분이 잘 이해가 안됐는데, sisobus님의 코드에선 now+=(M-1) 이라는 식으로 매번 시작에서 얼마나 떨어져있는지를 결정한다.

이것은 내 개인적인 생각으로는, now=(now-1)+M;이라고 생각하면 더 쉬운 것 같다.
이미 한 명을 제거 했으니, 시작점 부터 시작할 때, now-1명을 지나치면 다음 시작점이 될 것이고, 거기서 부터 M만큼 가서 다음 차례인 사람을 찾으면 되는 것이다.

**** 시간 초과가 나서 코드를 점검했는데도 시간초과의 원인을 찾지 못하고 있었다.
분명 내 코드는 nlogn+nlogn * logn 의 시간복잡도를 가지고 있어서 당연히 1초안에 들어올 수 밖에 없는데... 실제로 문제의 시간 제한은 2초라 통과할 수 밖에 없을텐데...
그러다 정말 감사하게도 문득 생각이 났다. interval이 1보다 큰데, 나중에 한 개 남으면 어떡하지? 이분 탐색할 때.. 정확히 뭐가 문제인지는 모르겠지만 일단 예제로 1 3을 넣어봤다.
그랬더니 답이 출력되다 말고 무한루프에 빠지는 것 같았다.

바로 이거다. 시간초과가 났을 때는 시간 복잡도 뿐만 아니라 무한 루프에 빠질 경우가 있는지도 생각해봐야 하는 것이다! 감사합니다!

이제 정확히 왜 무한 루프에 빠지는 지 점검해보고 고쳐야겠다.

아 일단, 예제 1 3에 대한 무한 루프에 빠지는 원인은 Fenwick Tree에 있었다. 이 경우에, 3%1==0 이기 때문에 Fenwick Tree에서 pos가 0인 경우에 -1을 add하려고 하는데, pos가 0이라 무한 루프에 빠지는 것이다.
그래서 m%n==0 ? n : m%n처리를 해줘야한다.

그리고 위에서 떠올랐던 문제가 될 것 같은 부분은 바로 위의 코드와 똑같은
interval%i==0 ? i : interval%i 때문에 문제가 되지 않는다는 것을 알았다. 나는 마지막에 한 명의 사람만 남았을 때 interval이 1보다 크면 이분탐색에서 그 사람을 못 찾을 거라고 생각했는데, 위의 코드 때문에 interval은 1로 설정되고 찾을 수 있다!

정말 좋은 문제다!