문제의 시간 제한이 매우 애매한 곳에 걸려 있습니다. 요세푸스 시리즈를 봤을 때 이 문제는 O(nlogn)의 풀이를 요구하는 버전인 것으로 보이지만, 널리 알려진 것처럼 라이브러리 함수에 의존하는 O(n^2) 풀이가 여전히 700ms로 통과됩니다. 로직이 같아도 조금만 비효율적이거나, 언어에 따라서 불가능할 수도 있습니다.
n 제한을 변경할 수는 없으니, 시간 제한을 바꿔서 둘 중 하나를 택해야 할 것으로 보입니다. 제한을 0.3초 수준으로 줄여 이러한 풀이들이 모두 막히게 하거나 (하지만 이것은 O(n^2)이 통과된다는 소문을 듣고 온 수많은 사람들을 배신하게 됩니다), 10초 정도로 늘려 이 로직을 아무리 비효율적으로 짜더라도 통과될 수 있게 만들 수 있습니다.
또는 이 문제를 채점 준비중으로 만들어 봉인하고, 새로운 n 제한의 문제를 이 자리에 끼워넣는 것도 하나의 방법일 것 같습니다.
djm03178 3년 전 1
문제의 시간 제한이 매우 애매한 곳에 걸려 있습니다. 요세푸스 시리즈를 봤을 때 이 문제는 O(nlogn)의 풀이를 요구하는 버전인 것으로 보이지만, 널리 알려진 것처럼 라이브러리 함수에 의존하는 O(n^2) 풀이가 여전히 700ms로 통과됩니다. 로직이 같아도 조금만 비효율적이거나, 언어에 따라서 불가능할 수도 있습니다.
n 제한을 변경할 수는 없으니, 시간 제한을 바꿔서 둘 중 하나를 택해야 할 것으로 보입니다. 제한을 0.3초 수준으로 줄여 이러한 풀이들이 모두 막히게 하거나 (하지만 이것은 O(n^2)이 통과된다는 소문을 듣고 온 수많은 사람들을 배신하게 됩니다), 10초 정도로 늘려 이 로직을 아무리 비효율적으로 짜더라도 통과될 수 있게 만들 수 있습니다.
또는 이 문제를 채점 준비중으로 만들어 봉인하고, 새로운 n 제한의 문제를 이 자리에 끼워넣는 것도 하나의 방법일 것 같습니다.