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

1158번: 요세푸스 문제

 

문제

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

1158번: 요세푸스 문제

 

 

풀이

요세푸스라는 잘 알려진 문제다. 일렬로 나열된 N개의 숫자들을 모두 사라질 때까지 K번째 마다 없앤다고 생각하면 된다. 큐(queue)라는 자료구조를 사용하면 쉽게 풀 수 있다. 큐는 FIFO(First In First Out), 즉 선입선출로 차례가 아닌 숫자는 뒤로 보내 다시 차례를 기다리도록 한다. 출력 조건 때문에 큐에 하나의 수를 남겨놓을 때까지 반복하도록 코드를 작성했다.

 

따라서 cnt라는 변수를 만들어 가리키는 횟수를 증가시켜 가며 진행한다. 횟수가 K로 나누어 떨어진다면 해당하는 front를 출력하고 queue에서 pop 한다. 나누어 떨어지지 않는다면 queue에 front를 추가해 다시 대기하도록 한 후, pop 한다.

 

출력 형식이 수 다음에 ", "가 나오는데 마지막엔 ">"가 나와야 하므로 큐에 한 개는 남겨두었고 마지막에 출력형식에 맞춰 출력해 주었다.

 

 

코드

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n, k;
  cin >> n >> k;
  queue<int> q;
  for (int i = 1; i <= n; i++)
    q.push(i);
  cout << '<';
  int cnt = 0;
  while (q.size() > 1) {
    cnt++;
    if (cnt % k) {
      q.push(q.front());
      q.pop();
    } else {
      cout << q.front() << ", ";
      q.pop();
    }
  }
  cout << q.front() << ">\n";
  return 0;
}