전산학이나 수학에서 요세푸스 문제(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번째 위치한 사람이 마지막으로 제외되게 된다.
이 순열은 역사가 요세푸스가 겪은 일화에서 유래하였다.
출처 : https://ko.wikipedia.org/wiki/%EC%9A%94%EC%84%B8%ED%91%B8%EC%8A%A4_%EB%AC%B8%EC%A0%9C
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.util.*; | |
| import java.io.*; | |
| /** | |
| * https://www.acmicpc.net/problem/11866 | |
| * BOJ 백준온라인져지 11866 조세퍼스 문제 0 풀이 | |
| */ | |
| class Main { | |
| public static void main(String[] args) throws IOException{ | |
| BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); | |
| BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); | |
| String str1[] = br.readLine().split(" "); | |
| int N = Integer.parseInt(str1[0]); | |
| int M = Integer.parseInt(str1[1]); | |
| int array[] = new int[N+1]; | |
| for(int i = 1; i<=N; i++){ | |
| array[i] = i; | |
| } | |
| bw.write("<"); | |
| int result = 0, idx = 0; | |
| for(int i = 1, cnt = 0; i<N; i++){ | |
| cnt = 0; | |
| while(cnt != M){ // M만큼 다음의 숫자 | |
| idx++; | |
| if(idx == N+1) idx = 1; // 배열의 최대 index를 넘어가면 1로 변경해준다. | |
| if(array[idx] > 0) cnt++; // 배열의 요소가 제외된 것이 아니라면 cnt를 1 올려준다. | |
| } | |
| bw.write(array[idx] + ", "); | |
| array[idx] = 0; | |
| } | |
| while(array[idx] == 0){ | |
| idx++; | |
| if(idx == N+1) idx = 1; | |
| } | |
| bw.write(array[idx] + ">"); | |
| bw.flush(); | |
| } | |
| } |
'IT > 알고리즘' 카테고리의 다른 글
| BOJ 백준온라인져지 1004 어린 왕자 풀이 (0) | 2017.11.30 |
|---|---|
| BOJ 백준온라인져지 1002 터렛 풀이 (0) | 2017.11.30 |
| BOJ 백준온라인져지 10845 큐 풀이 (0) | 2017.11.29 |
| BOJ 백준온라인져지 2504 괄호의 값 풀이 (0) | 2017.11.28 |
| BOJ 백준온라인져지 1874 스택 수열 풀이 (0) | 2017.11.27 |