본문 바로가기
Algorithm/Baekjoon

Baekjoon 11866 요세푸스 문제 0 JAVA

by Hunveloper 2022. 2. 6.
728x90
 

11866번: 요세푸스 문제 0

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

www.acmicpc.net

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

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

출력

예제와 같이 요세푸스 순열을 출력한다.

코드
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		int n=sc.nextInt(), k=sc.nextInt(), remaining=n,j=0;
		int [] arr = new int[n];
		for(int i=0;i<n;i++)
			arr[i]=i;
		sb.append("<");
		while(remaining>0) {
			int cnt=0;
			while(cnt<k) {
				if(arr[j]!=-1)
					cnt++;
				if(cnt==k)
					break;
				j++;
				j%=n;
			}
			sb.append((int)(j+1)+", ");
			arr[j]=-1;
			remaining--;
		}
		sb.delete(sb.length()-2, sb.length());
		sb.append(">");
		System.out.println(sb.toString());
	}
}
728x90
728x90

'Algorithm > Baekjoon' 카테고리의 다른 글

Baekjoon 2178 미로 탐색 JAVA  (0) 2022.02.07
Baekjoon 2164 카드2 JAVA  (0) 2022.02.07
Baekjoon 14500 테트로미노 JAVA  (0) 2022.02.05
Baekjoon 1260 DFS와 BFS JAVA  (0) 2022.02.05
Baekjoon 1244 스위치 켜고 끄기 JAVA  (0) 2022.02.05

댓글