요세푸스 문제
실버 II의견: 0
\(1\)번부터 \(N\)번까지 \(N\)명의 사람이 원을 이루어 앉아 있고, 양의 정수 \(K\)가 주어진다. 이제 순서대로 \(K\)번째 사람을 차례로 제거한다.
한 사람이 제거되면 남은 사람들로 다시 원을 이루어 이 과정을 반복하며, 모든 사람이 제거될 때까지 계속한다. 사람들이 제거되는 순서를 요세푸스 순열 \(\langle N, K \rangle\)라 한다.
예를 들어 \(\langle 7, 3 \rangle\)에서는 \(1\)번부터 세어 세 번째인 \(3\)번이 먼저 제거되고, 이어서 \(6, 2, 7, 5, 1, 4\)번이 차례로 제거된다.
\(1 \le K \le N \le 5\,000\).
첫째 줄에 두 정수 \(N\), \(K\)가 공백으로 구분되어 주어진다.
제거되는 순서대로 \(N\)개의 정수를 한 줄에 공백으로 구분하여 출력한다 (요세푸스 순열).
7 3
3 6 2 7 5 1 4
\(\langle 7, 3 \rangle\)의 제거 순서는 \(3, 6, 2, 7, 5, 1, 4\)이다.
1 1
1
사람이 한 명뿐이므로 \(1\)번이 제거되고 끝난다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
요세푸스 문제
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
요세푸스 문제