[platinum1][해설안봄,분류안봄] 1179 마지막 요세푸스 문제 (좀 이상하게 푼듯)

https://www.acmicpc.net/problem/1179

 

 

문제를 풀 때 논리적으로 맞긴 한데 약간 이상해보이는 풀이라 맞을까 불안해하며 풀었는데 다행히 1트만에 성공했다...!

땅따먹기 문제때문에 이제 동고쇼에는 진절머리가 났는데  난이도에 비해 무난히 풀려서 정말 다행이다..

 

구간을 적절히 나눠 이분탐색으로 풀었는데 풀고 난이도 기여에서 푼사람들 리뷰를 보니 이분탐색으로 푼 사람은 없는 것 같다..

특정 공식이 있는 것같은데 공식을 몰라도 풀 수 있다는 점에서 좋았다. 높은 티어로 갈수록 솔루션은 단일화 되가는 경향이 있는데 말이다.

아이디어는 그렇게 어렵지 않다.   

우선 처음에 [1~ N / 2 ], [N / 2 + 1 ~ N]  두구간으로 나눈다.  각 구간의 숫자수는 각각 N / 2개 씩 있을 것이다.

여기서 K번째 마다 지운다면  남은 숫자수 / K 만큼 삭제할 수 있을 것이다. 

 

이렇게 삭제가 가능할 것이다.   

 구간1의 남은 숫자갯수를 cnt1 이라하면 cnt1 -= cnt1 / K 가 될 것이다.

그럼 구간2는 몇개를 지울 수 있을까?

구간1과 K개씩의 간격은 동일하지만, 처음 지우는 시작 포인트가 다르기 때문에 구간1과는 삭제갯수가 달라질 수 있다.

구간1에서 9 까지 지우고, 10은 건너뛰었으므로, 구간2에서는 2번째부터 지울 수 있게 될 것이다.

따라서 (N - startPoint) / K + 1 개 를 지울 수 있다. 

 

구간2에서 마지막 18까지 지우고 나면 다시 구간1로 넘어갈 것이다. 이때 19,20 은 건너 뛰므로, 구간1은 첫번째 부터 지울 것이다.

 

 

이때 cnt1 =  7 인 상태이다.  여기서 주의해야 할 점은 무슨 숫자가 지워졌나가 중요한 게 아니라 숫자가 몇개가 남았냐가 중요하다.

방금 19,20 은 건너뛰었으므로, 남은 7개 숫자중 첫번째 숫자부터 지울 수 있을 것이다. 

  마찬가지로 (N - startPoint)/ K + 1 만큼 지울 수 있으므로 (7 - 1) / 3 + 1 개만큼 지울 수 있을 것이다. 그러면 cnt1 = 7 - 3 = 4 가 될 것이다.

 

이제 구간2로 넘어가야하는데 이번엔 건너뛰는 숫자가 없으므로 , 구간2에 남아잇는 숫자중 3번째 부터 시작한다.

(7 - 3) / 3 + 1  = 2 개 지울 수 있다. cnt2 = 5

이런식으로 삭제해 나가면 cnt1, cnt2 는 점점 줄어나가고  둘중하나가 먼저 0이 될 것이다. 나중에 0이 되는 쪽이 마지막 까지 살아남는 사람이 있는 구간이 될 것이다.

 

근데 여기서는 구간으로만 계산했으므로, 마지막사람이 어느 구간안에 있다는 것만 알고, 정확히 어딨는지는 모른다.

하지만 구간을 점점 좁혀갈 수는 있다,. 이분탐색 처럼 말이다.

우리는 방금 11~20 구간에 마지막 숫자가 있는 것을 알았다. 그러면 범위를 좁히기 위해 이 구간을 반으로 자른다. 11~15 , 16~20이 될 것이다. 거기에 남은 숫자들의 구간 1~10 까지 구간은 3개가 된다.

cnt1 = 10, cnt2 = 5, cnt3 = 5 상태에서 방금한대로 숫자를 지워나가면 된다. 

마지막 살아남는 사람이 있는 구간은 구간2 , 구간3 둘중 하나가 될 것이다. 

그 구간이 구간2라고 하면, 이 구간을 또 둘로 나눈다.

이번엔 구간이 4개로 나눠진다. 만약 이번엔 구간3 이 마지막으로 남는 다고 해보자.

그럼 다음 구간은 이렇게 된다.

 

이와같이 처음 시작할 때 구간은 2개이고, 그다음은 구간의 갯수는 3개 혹은 4개가 된다.

이렇게 계속 진행해나가면서 살아남은 구간은 반으로 나눠가면 살아남은 구간의 숫자가 한개일 때가 올 것이고,  이때가 정답이다.

 

구간3이 살아남아서  14, 15로 쪼개지고,   마지막으로 한번더 계산했을 때 살아남는 구간이 구간2면 14, 구간3이면 15가 답일 것이다.

 

요약하면 계산할 때 포인트는 구간마다 startpoint를 알고, 구간의 남은 숫자갯수를 알면 몇개를 지울수 있을지 알 수 있다는 것이다. startpoint는 전 구간의 마지막 삭제 숫자로부터 몇개나 뛰어넘었는지가 영향을 끼친다.

 

이런식으로 계산을 할 때 K번째 마다 삭제하므로 구간들을 한바퀴 돌때마다 남은 숫자는 N * (K - 1) / K 이다.    가장 숫자가 드문드문 지워지는 K = 90 이고,  (89/90) 를 3000~4000번 제곱하면 10^(-15)정도 나온다. N = 10 ^ 15 일 때 마지막 살아남는 구간 계산은 O(3000~4000) 정도 된다는 말이다. 

여기에 절반씩 구간이 좁혀지므로, 이분탐색으로 log2(10^15) = 50  정도이고,  O(3000*50 ~4000*50)정도로 계산시간은 괜찮다.