이동식 저장소

크리스마스 이브..인데 이렇게 분위기 안 나는 해는 처음이다. 코딩이나 합시다.

$N$이 무려 20억이다. 선형 탐색하지 말라는 강력한 신호.

이번 글은 나의 풀이와 좋은 풀이를 비교해 보도록 하겠다. 왜냐면 원래는 안 되는 방식으로 풀었기 때문..

나의 접근

아이들이 놀이기구를 타는 순서는 일정 주기마다 반복된다. 그 주기는 바로 모든 놀이기구의 운행시간의 최소공배수($LCM$이라 하자). 따라서 $N$번째 아이가 아닌 $N^{\prime }=N\mathrm{mod}LCM$번째 아이가 타는 놀이기구를 구해도 된다. 이러면 탐색 범위가 줄어들기 때문에 선형 탐색을 아슬아슬하게 할 수 있다.

이제 다음의 함수를 정의한다.

$f(t)$: $t$초까지 놀이기구를 탄 아이들의 총 수

처음 시간을 0초라 하면, 처음에 모든 놀이기구가 비어 있기 때문에 $f(0)=M$이다. $N^{\prime }$번째 아이가 타는 놀이 기구를 특정하기 전에 일단 타는 시간부터 구해야 한다.

각 놀이기구는 시간이 운행 시간 $dur$의 배수 시간일 때마다 비어 있다. 예를 들어 운행 시간이 $2$초인 놀이기구는 0초, 2초, 4초, ...일 때 비어 있다. 따라서 $f(t)=f(t-1)+(t의약수인dur의개수)$이다. 그러면 구하는 시간은 $f(t-1)<N^{\prime }\le f(t)$를 만족하는 최초의 $t$이다.

이제 놀이 기구의 번호를 구하자. 우리가 구하는 놀이기구는 시간 $t$초에서 $N^{\prime }-f(t-1)$번 째로 비어있는 놀이 기구이다. 이건 그냥 운행 시간을 순회하면서 $t$의 배수인 $N^{\prime }-f(t-1)$번째 놀이 기구의 번호를 구하면 된다.

이 풀이가 비효율적인 이유

$f(t)$를 구하는 과정에서 선형 탐색을 사용하고 있다. $N$을 $N^{\prime }$으로 줄였다고는 하나 $N^{\prime }$도 여전히 매우 크기 때문에 선형 탐색을 하면 좋지 않다.

더 나은 풀이

식을 보면 알겠지만 $f(t)$는 감소하지 않는 함수이므로 이분 탐색을 적용할 수 있다. 이분 탐색을 하려면 $f(t)$를 상수 시간에 구할 수 있어야 한다. 나도 이분 탐색 생각을 하긴 했는데 $f(t)$를 어떻게 구해야 할지 잘 모르겠어서 저렇게 푼 것이다.

사실 $f(t)$는 매우 쉽게 구할 수 있다. $0$초에 타는 아이를 제외하면, 운행 시간이 $dur$인 어떤 놀이기구에 시간 $t$초까지 탄 아이의 수는 $\frac{t}{dur}$의 몫이다. 따라서 $f(t)=M+\sum \frac{t}{dur}$의 정수부분이다. $M$은 $0$초에 타는 아이를 고려한 것이다. 여기서 중복되는 $dur$의 값을 한번에 처리해 주면 더 좋다.

이제 $f(t)$를 구할 수 있으므로 이분 탐색을 수행하여 $f(t-1)<N^{\prime }\le f(t)$를 만족하는 최초의 $t$를 찾을 수 있다. 그 뒤의 과정은 위에서와 같다.

왜 이렇게 풀지 못했나?

관찰력의 부재라고 봐야 할 듯? 노트에 표까지 다 그려놨는데도 쉬운 방법이 생각이 안 나서.. 특정 시간에 탄 사람 수를 구하려고 생각하니까 나눗셈이 생각이 안 났다.

이건 그냥 기념으로 남겨놓기로 했다.