백준 #1215 잘못 작성한 요세푸스 코드

꽤 재미있는 문제였던 것 같습니다.  요세푸스 문제를 해결할 때, 큐를 이용해서 매번 풀었는데, 모듈라 연산으로 풀 수도 있었구나를 생각하게 만들었네요.  Platinum V 문제이긴 하지만, 적절한 알고리즘이 알려진 상태가 아니라는 점을 감안하면 좀 더 난이도를 높게 주는 것이 맞을 듯 하네요.  그런데 오리지널 코드 그대로도 통과가 되는 것 같은데, 만약 그렇다면, 오히려 난이도가 떨어져야 할지도 모르겠네요.

 

Original Josephus Problem.

 

이번문제는 다음의 코드를 적절하게 바꾸어서 같은 결과를 나오게 하는 것입니다.  결과 검증하기도 좋습니다.  실제 코드를 실행해보면, 아주 큰 수에 대해서 그래도 기다려줄 수 있는 속도가 나오니까요.

 

  Invalid Josephus Code

요세푸스 문제는 큐를 배울 때, 자주 등장하는 문제입니다.  큐를 구현하고, 큐에 데이터를 넣고 빼는 것을 배우게 됩니다.  사실 이 문제는 요세푸스 문제와는 크게 관계가 없습니다.  위의 코드를 이해하고, 그것을 수학적으로 어떻게 해결하는가가 중요합니다.

 

일단 위의 코드를 수식으로 표현하면 다음과 같습니다.

 

$$r=\sum _{i=1}^n(k\mathrm{mod}i)$$

 

이 식을 어떻게 바꿀 것인 가가 관건입니다.

 

나머지값은 어떻게 계산이 될까요?  $k\mathrm{mod}i=k-i\cdot a$ 형태로 최대의 a 값을 찾으면 됩니다.  $k\mathrm{mod}i=k-i\cdot \lfloor k/i\rfloor$ 와 같이 최대 정수값을 반환하는 floor 함수를 쓰면 됩니다.  C 언어에서는 floor 함수는 아주 자주 쓰입니다.  정수 나눗셈이 floor 함수 기능을 합니다.  (단, 양수에서만)

 

그러면 위의 식은 다음과 같이 변형될 수 있습니다.

 

$$r=\sum _{i=1}^{n}k-i\cdot \lfloor k/i\rfloor =k\cdot n-\sum _{i=1}^{n}i\cdot \lfloor k/i\rfloor$$

 

식을 변형해서 나머지 연산을 없앴지만, 아직까지는 n번 합을 계산하는 것이 그대로 남아있습니다.  그렇게 해서는 앞에 식하고 크게 다를 바가 없습니다.  자 이제 k/i 를 눈여겨 보도록 하죠.  $f(x)=\lfloor k/x\rfloor$ 라는 함수를 생각해보도록 하죠.

 

k=17 일 때, 그래프를 그려보면 다음과 같습니다.

 

f(x) = floor(17/x)

함수 값이 1인 숫자의 범위는 9에서 17까지입니다.  2인 숫자의 범위는 6에서 8까지이고요.  그런데, x=1 일 때의 값은 17, x = 2일 때의 값은 8입니다.  둘의 연관관계가 보이죠.  즉, 1부터 $\sqrt{k}$ 까지의 숫자만 처리하면, 반대쪽도 같이 처리할 수 있습니다.

 

처음에 $O(K)$ 알고리즘이 $O(\sqrt{K})$ 알고리즘으로 변했습니다.  이건 매우 중요한게, 이번 문제는 N, K 값이 ${10}^9$ 까지입니다.   10억정도의 숫자면 아마 아슬아슬하게 통과될 수도 있겠죠.  하지만, $O(\sqrt{K})$ 알고리즘을 이용하면 0ms 의 결과를 낼 수 있습니다.  제가 맥북에어에서 테스트해본 결과 오리지널로 처리하면, 2,944ms가 걸렸습니다.  그에 비해서 제가 제출한 코드는 3ms가 걸렸네요.  (백준에서 AC 받은 것으로는 0ms)

 

맞은 사람 코드로 1등을 해서, 기록용으로 남겨둘께요.

 

1등~