[algospot] JOSEPHUS

문제링크 입니다

🚀 [JOSEPHUS] 문제 😊😊😊😊😊

1세기에 살던 역사학자 조세푸스는 로마와의 전쟁에서 패해 N - 1명의 동료 병사들과 함께 출구가 없는 동굴에 포위당했다고 합니다. 동료 병사들은 로마에 항복하느니 차라리 자살하자고 결의했고, 포위당한 N명의 사람들이 모두 원형으로 둘러선 뒤 순서대로 자살하기로 했습니다. 한 사람이 자살하면, 다음에는 그 사람으로부터 시계 방향으로 K번째 살아 있는 사람이 자살하는 것입니다.

조세푸스의 책에 따르면 조세푸스와 다른 병사 하나만이 살아남았을 때 이들은 마음을 바꿔 로마에 항복해서 살아남았다고 합니다. 마지막 두 명 중 하나가 되기 위해서는 조세푸스는 첫 번째 병사로부터 몇 자리 떨어진 곳에 있어야 했을까요?

🔑 [풀이]

list를 이용하여 간단하게 풀수 있는 문제였습니다. 코드참조

⌨️ 입력

입력의 첫 번째 줄에는 테스트 케이스의 개수 C (C≤50)가 주어집니다. 각 테스트 케이스는 두 개의 정수 N, K로 주어집니다(3≤N≤1000, 1≤K≤1000).

🖥 출력

각 테스트 케이스에 두 개의 정수로, 마지막 살아남는 두 사람의 번호를 오름차순으로 출력합니다. 첫 번째로 자살하는 병사의 번호가 1이며, 다른 사람들의 번호는 첫 번째 병사에서부터 시계 방향으로 정해집니다.

🖱 입력 예제

2
6 3
40 3

💻 출력 예제

3 5
11 26

💎 전체 코드는 다음과 같습니다.

//
//  JOSEPHUS.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/11/28.
//

#include <iostream>
#include <fstream>
#include <algorithm>
#include <list>

using namespace std;
ifstream fin("JOSEPHUS.txt");

void josephus(int N, int K){
    list<int> survivors;
    for(int i=1; i<=N; i++){
        survivors.push_back(i);
    }
    // 죽을사람의 포인터 ㅜㅜ
    list<int>::iterator kill = survivors.begin();
    while(N>2){
        // erase 는 kill사람을 없애고 다음 사람을 포인터로 가르킨다.
        kill = survivors.erase(kill);
        N--;
        // 끝에가면 다시 첨으로 돌아감.
        if(kill == survivors.end()) kill = survivors.begin();
        // k번 다음사람을 가르킨다.
        for(int i=0; i< K-1; i++) {
            kill++;
            // 끝에가면 다시 첨으로 돌아감.
            if(kill == survivors.end()) kill = survivors.begin();
        }
    }
    cout << survivors.front() << " " << survivors.back() << endl;
}
int main(){
    int test_case;
    fin >> test_case;
    for(int test=0; test<test_case; test++){
        int N; // 사람수
        int K; // K번째가 죽음
        fin >> N >> K;
        josephus(N,K);
    }
}