[백준 11866] 요세푸스 문제0

요세푸스 문제0

문제 설명

N,K를 입력 받고 원에서 K번째 사람을 계속 제거한다.
이 때 제거 된 사람의 번호를 출력 시킨다.

알고리즘

1. 값을 입력 받고 , N 만큼 vector에 넣는다.
2. 출력하고자 하는 index라는 변수에 K-1을 더한다.
3. 더하는 동작을 반복문 안에서 반복하다 보면 index범위를 넘어가는 경우가 있기 때문에 벡터의 사이즈 만큼 범위에 해당 되도록 뺀다.
4. index 벡터 값을 출력 시킨다.
5. 벡터에서 해당 변수를 삭제 시킨다.

---

#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;

int main()  5
{    
    int num =0,K=0;
    cin >> num>>K;
    vector < int> v;
    for (int i = 0; i < num; i++)
        v.push_back(i+1);
    int index = 0;
    cout << "<";
    while (num!=1)
    {    
        index += K - 1;//이동할 index 
        while (index >= v.size())//범위를 넘어선 경우 계속 크기를 빼서 알맞은 index를 찾아줌 
            index -= v.size();
        cout << v[index] << ", ";//값 출력
        v.erase(v.begin() + index);//해당 원소 삭제 
        num--;
    }
    cout<< v[0]<< '>';//마지막 부분은 ,를 출력하지 않기 위해 따로 출력
    return 0;
}

고찰

이번 문제는 벡터가 값을 지우면 알아서 정렬 되는 특징을 이용해서 만들 수 있었다.