문제2024--요세푸스 문제

2024: 요세푸스 문제

[만든사람 : ]
시간제한 : 1.000 sec  메모리제한 : 128 MiB

문제 설명

전산학이나 수학에서 요세푸스 문제(Josephus problem) 혹은 요세푸스 순열(Josephus permutation)은 다음과 같이 정의한다. 

\(n\)과 \(k\)가 자연수이고, \(k < n\)이라고 가정한다. \(n\)명이 동그랗게 모여있을 때 임의의 한 명부터 순서를 세어 \(k\)번째 사람을 모임에서 제외한다. 남은 \(n-1\)명에서 다시 다음 사람부터 순서를 세서 \(k\)번째 사람을 모임에서 제외한다. 이것을 아무도 남지 않을 때까지 계속해서 반복한다. 이때 모임에서 제외되는 사람의 순서를 \((n, k)\) 요세푸스 순열이라고 하며 마지막으로 제외되는 사람을 구하는 문제를 요세푸스 문제라고 한다. 예를 들어 \((7,3)\) 요세푸스 순열은 \({3,6,2,7,5,1,4}\)이며 \(4\)번째 위치한 사람이 마지막으로 제외되게 된다.

 이 순열은 역사가 요세푸스가 겪은 일화에서 유래하였다.



입력 설명

첫째 줄에 \(N\)과 \(K\)가 빈 칸을 사이에 두고 순서대로 주어진다. \((1 \le K < N \le 5,000)\)

출력 설명

요세푸스 순열을 공백을 기준으로 출력한다.

입력 예시 Copy

7 3

출력 예시 Copy

3 6 2 7 5 1 4 

게시판

작성자제목(댓글)
글이 없습니다.

출처/분류