(매일 BOJ) C++ 11866번 요세푸스 문제 0

이번 문제는 실버 4 난이도의 요세푸스 문제 0이다.

 

 

문제의 접근법부터 살펴보자.

 

11866번(요세푸스 문제 0)은 원형으로 앉아있는 N명의 사람 중 K번째 사람을 반복적으로 제거할 때, 제거되는 순서를 구하는 문제이기에, 자료구조(리스트, 큐 등)를 이용해 사람들을 순서대로 저장한 뒤, K번째마다 해당 인덱스의 사람을 제거하며, 제거된 순서를 기록하면 된다.

매번 K번째 사람을 찾을 때마다 남은 사람 수에 따라 인덱스를 갱신(모듈로 연산 활용)하고, 사람을 제거한 후에도 원형 구조처럼 인덱스를 순환시키는 것을 반복해서 N명이 모두 제거될 때까지 과정을 이어가면, 요구하는 결과를 얻을 수 있습니다.

 

C++ vector 의 메서드 중 erase 를 사용하면 인덱스의 사람을 제거할 때, 제거된 공간이 자동으로 앞으로 옮겨지는 것을 사용하면 쉽게 해결할 수 있다.

 

아래는 작성한 코드이다.

#include <bits/stdc++.h>
using namespace std;

int main (void){
    ios::sync_with_stdio(0); cin.tie(0);

    int N,K;
    cin >> N >> K;
    vector<int> v;
    for (int i = 1; i < N+1; i++){
        v.push_back(i);
    }
    vector<int> result;
    int temp = 0;
    while (v.size()){
        temp = (temp + K - 1 ) % v.size();
        result.push_back(v[temp]);
        v.erase(v.begin() + temp);
    }

    cout << '<' << result[0];
    for (int i = 1; i < N; i++){
        cout << ", " << result[i];
    }
    cout << '>';
}