BOJ 4906 Musical Chairs

문제 링크:

문제 내용

$1, 2, \cdots, N$ 의 번호가 매겨져 있는 $N$ 명의 사람이 번호 순서대로 원 모양으로 앉아 있습니다. 1번부터 시작하여 번호가 증가하는 방향으로 세어 $D$ 번째 사람을 원에서 제거하는 것을 원에 한 명만 남을 때까지 반복합니다.

원에 남는 사람의 번호를 구하세요.

여러 개의 테스트 케이스가 주어집니다. 각 테스트 케이스에 대해, $N$ 과 $D$ 의 값이 한 줄에 순서대로 주어집니다. ( $1 \le N, D < 10^6$ ) 입력은 0 0으로 종료되며, 이 줄은 처리하지 않습니다.

모든 테스트 케이스의 $N$ 의 합은 $6 \times 10^6$ 을 초과하지 않습니다.

각각의 테스트 케이스에 대해, $N$ , $D$ , 그리고 정답을 한 줄에 출력합니다.

스포일러

이 문제는 유명한 요세푸스 문제입니다.

사람의 번호를 0-based로 바꾸고 생각해 봅시다. $N$ 명이 있을 때 첫 턴에는 $x = (D-1) \bmod N$ 번 사람이 탈락하며, $x$ 보다 작은 번호를 가진 사람이 $x$ 명, 큰 번호를 가진 사람이 $N-x-1$ 명이 남습니다.

이제 $N-1$ 명이 있을 때의 승자를 $k$ 라고 하면, 이 과정을 역으로 진행하여 $N$ 명이 있을 때의 승자의 번호를 구할 수 있습니다. 구체적으로 답은 다음과 같습니다.

$N = 1$ 이면 답은 0이므로, 이 과정을 $N = 1$ 에서부터 역순으로 진행할 수 있습니다. 테스트 케이스 별로 $\mathcal{O}(N)$ 시간이 소요됩니다.

Last updated on 2025년 9월 18일 18:00:10