n과 k가 자연수이고, k < n이라고 가정한다. n명이 동그랗게 모여있을 때 임의의 한 명부터 순서를 세어 k번째 사람을 모임에서 제외한다. 남은 n-1명에서 다시 다음 사람부터 순서를 세서 k번째 사람을 모임에서 제외한다. 이것을 아무도 남지 않을 때까지 계속해서 반복한다. 이때 모임에서 제외되는 사람의 순서를 (n, k) 요세푸스 순열이라고 하며 마지막으로 제외되는 사람을 구하는 문제를 요세푸스 문제라고 한다.
예를 들어 (7,3) 요세푸스 순열은 {3,6,2,7,5,1,4}이며 4번째 위치한 사람이 마지막으로 제외되게 된다.
출처 : 위키백과
k = 2일 때의 문제가 cses 사이트의 문제로 등록되어 있는데 생각한 것보다 복잡한 문제인 것 같다.
파이썬 리스트를 이용해서 풀어보려고 했으나 리스트를 이용하는순간 퍼포먼스를 만족 못하는 듯하다 ㅠㅠ..
어떤 매커니즘에의해 숫자를 프린팅 해야 하는 것 같은데 더 고민해보아야 할 문제다.
반응형