1168번 - 요세푸스 문제 2
세그먼트 트리로 어찌어찌 풀었는데
더 쉽게 풀 방법은 없는건가요???
세그먼트 트리 등의 자료구조를 쓰는 것이 정해인 것으로 생각되나, 안타깝게도 단순히 시뮬레이션을 하는 O(nk) 풀이가 통과된다고 합니다. 대단히 유감스러운 부분입니다.
어제 시간 제한이 바뀌어서 더 이상 O(nk)로 풀 수 없는 문제가 되었습니다.
vector나 Python list를 써도 시간 복잡도는 여전히 O(nk)입니다. 중간에 있는 원소를 삭제하면 그 이후에 있는 모든 원소를 하나하나 앞으로 옮겨야 되기 때문입니다. 따라서 이제는 시간 초과가 날 것입니다.
댓글을 작성하려면 로그인해야 합니다.
hwy16016 3년 전
세그먼트 트리로 어찌어찌 풀었는데
더 쉽게 풀 방법은 없는건가요???