[백준][1158번][C++] 요세푸스 문제

https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

오늘 가볍게 풀어본 문제는 요세푸스 문제이다.

 

요세푸스 문제에는 스토리가 있다.

요세푸스는 유대와 로마가 전쟁일 때 유대군 장교로 참전한 적이 있었는데

유대군이 전쟁에서 밀리자 항복대신 차라리 자살을 하자는 동료들의 의견이 강세였다고한다.

근데 그냥 자살하기는 뭐했는지 원모양으로 둘러서서 정해진 순서만큼 건너뛰면서 죽이기로 했다고 한다.

하지만 동료들과 다르게 현명한 요세푸스는 자살하고 싶지 않아서 어디에 서야지 끝까지 살아남을 수 있는지를 찾아서 마지막까지 살아남아 로마에 항복했다는 이야기이다.

근데 그냥 죽기싫다고 이야기하면 되는거 아닌가..? 아무래도 옛날에도 남자들 사이에서는 가오가 중요했던 것 같다.

요세푸스 이야기

요세푸스 문제 - 나무위키

자료구조 공부용으로 진작 풀어봤어야 했는데 처음에 PS 입문할 때 C로만 문제를 풀다보니깐 큐의 크기를 얼마나 줘야할지 애매하기도하고 자료구조 문제는 STL공부용으로 풀고싶어서 남겨놨던 문제이다.

이번에 C++로 넘어가면서 <vector> STL을 이용해서 풀어보았다.

 

알고리즘의 주된 구조는 다음과같다.

1.vector안에 첫번째 요소부터 하나씩 순서대로 탐색한다.

2-1. 만약 선택된 요소가 K번째 요소가 아니면 선택된 요소를 push_back하고 다음 요소를 탐색한다.

2-2. 만약 선택된 요소가 K번째 요소면 선택된 요소를 출력하고 다음 요소를 탐색한다.

3. N개의 요소를 출력했으면 탐색을 종료한다.

 

참고로 출력할 때 요소들 사이에 정확히 ", "를 출력하지 않으면 (띄어쓰기가 들어가있다) 틀리므로 문제를 꼼꼼히 읽는 습관을 가지자.

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

int main()
{
    vector<int> q;
    int N, K, count=0, p=0, now=1;
    scanf("%d %d",&N,&K);

    for(int i=1;i<=N;i++)
        q.push_back(i);

    printf("<");

    while(count!=N)
    {
        if(now==K)
        {
            printf("%d",q[p++]);
            count++;
            now=1;
            if(count!=N)
                printf(", ");
        }
        else
        {
            q.push_back(q[p++]);
            now++;
        }
    }

    printf(">");

    return 0;
}