Josephus Problem

문제 >

로마시대의 유대인 역사학자 플라비우스 요세푸스(Flavius Josephus)는 그의 저서 "유대 전쟁사"에서 그가 로마군에 포위된 동굴에서 41 명의 유대전사들 중에서 살아남은 이야기를 서술하고 있다. 유대전사들은 로마군에게 항복하느니 자살을 하겠다고 결정하고 모든 전사를 원형으로 배치시킨 다음 특정 위치부터 시작하여 원형을 따라 매 세번째 위치한 전사들 순서로 자살하기로 하였다. 이러한 자살 결정에 내심 반대하던 요세푸스와 다른 한 명의 동료는 제일 마지막으로 남는 두 자리의 위치를 재빠르게 계산하여 살아 남았다고 한다. 요세푸스 문제(Josephus problem)는 이렇게 41명을 원형으로 배치시키고 특정 위치를 1번이라고 하고 원형을 따라 순서대로 번호를 부여할 때, 마지막으로 살아남은 두 사람의 위치를 계산하는 문제이다. 두 사람의 위치는 각각31 번과 16 번이다.
이러한 요세푸스 문제의 변형된 여러가지 문제 중의 하나는 다음과 같다. 두 개의 자연수 n과 m 이 주어졌을 때, 먼저 1부터 n까지의 자연수를 원형으로 배치한다. 그리고 1부터 시작하여 m-1개의 수를 건너뛰고 m번째 수를 제거하고 그 다음 수부터 다시 시작하여 m번째 수를 제거하는 것을 반복하여 마지막에 한 개의 수가 남을 때까지 진행한다. 이 때 마지막으로 남은 숫자의 번호를 알고자 한다. 예를 들어 다음과 같이 n=10, m=3인 경우에는 마지막에 숫자 4가 남게 된다

이 문제를 해결하는 방법에는 여러가지가 있을 수 있다. 복잡하게는 점화식 (recursive equation) 을 세워서 해결할 수도 있다. 그러나 간단하게는 1차원 배열의 인덱스를 각 숫자라고 가정하고 위 그림과 같이 문제를 해결하는 상황을 그대로 구현하면서 해당하는 숫자를 제거하는 방식으로 문제를 해결할 수 있다.
두 개의 자연수 n과 m이 주어졌을 때, 위와 같이 변형된 요세푸스 문제를 해결하는 프로그램을 작성하시오.

 

입력 >

입력은 표준입력 (standard input)을 사용한다. 입력은 t개의 테스트 케이스로 주어진다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 t가 주어진다. 두 번째 줄부터 t개의 줄에는 한 줄에 한 개의 테스트 케이스에 해당하는 두 자연수 n,m (2 ≤ n ≤ 1,000, 1≤ m < n)이 주어진다. 두 자연수 사이에는 한 개의 공백이 있으며, 잘못된 데이터가 입력되는 경우는 없다.

 

출력 >

출력은 표준출력(standard output)을 사용한다. 입력되는 테스트 케이스의 순서대로 다음 중에 이어서 각 테스트의 결과를 출력한다. 각 테스트 케이스에 해당하는 출력의 첫 중에 입력되는 요세푸스 문제의 해답을 출력한다

 

입출력 예시 >

입력	출력
4 10 3 41 3 999 29 1000 1	4 31 266 1000

 

---

vector<int> n; //1 ~ num 까지의 자연수 들어있음
int num = 0; //n값
int gap = 0; //m값

int josephus(){
    int idx = gap-1; //초기 설정
    while(n.size()>1){ //하나만 남을때까지 반복
        n.erase(n.begin() + idx); //idx에 해당하는 자연수 제거
        idx = (idx+(gap-1) >= n.size() ? (idx+(gap-1))%n.size() : idx+(gap-1)); //idx값 설정
    }
    //결국 하나만 남을테니까 0번 출력
    return n[0];
}

idx 값을 설정할때, 현재 남은 숫자갯수보다 idx+gap이 더 커지면 안되므로, 앞으로 돌아서 빙글빙글 계속해서 돌게끔 만들었다.

 

이번 문제를 끝으로 알고리즘 수업 끝났음

야홋 ~!