6051 : 요세푸스 K (큰 N)
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N명 중에서 K번째마다 한 명씩 제거할 때, 마지막에 남는 사람의 번호(1-indexed)를 출력하시오.
N이 최대 1,000,000까지 주어지므로 시뮬레이션 없이 $O(N)$ 점화식을 사용해야 합니다.
점화식:
[제약 조건]
• $N$: $1 \le N \le 1{,}000{,}000$ (정수)
• $K$: $1 \le K \le 1{,}000{,}000$ (정수)
N이 최대 1,000,000까지 주어지므로 시뮬레이션 없이 $O(N)$ 점화식을 사용해야 합니다.
점화식:
f(1,k)=0, f(n,k)=(f(n-1,k)+k) mod n[제약 조건]
• $N$: $1 \le N \le 1{,}000{,}000$ (정수)
• $K$: $1 \le K \le 1{,}000{,}000$ (정수)
입력 설명
첫째 줄에 N과 K가 공백으로 구분되어 주어집니다. (1 ≤ N ≤ 1,000,000, 1 ≤ K ≤ 1,000,000)
출력 설명
마지막에 남는 사람의 번호(1-indexed)를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
7 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
4도움
점화식: f(n,k) = (f(n-1,k) + k) % n, f(1,k) = 0. 결과에 1을 더해 1-indexed로 변환합니다.