취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 15832번 문제인 Aku Negaraku이다.
문제는 아래 링크를 확인하자.

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

큐(queue) 자료구조를 이용하여 문제에 제시된 시뮬레이션을 진행하자.

매 M번째의 사람이 외국으로 나가는 것이지 매번 M명을 건너뛰고 다음 사람이 외국에 나가는, 즉 매 M+1번째의 사람이 외국으로 나가는 것이 아님에 유의해 구현하자.

주어진 문제는 Josephus problem와 같은 문제이므로, 더 효율적인 풀이에 관심이 있다면 다음 글(링크)을 읽어보자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <queue>
using namespace std;

int N, M;
queue<int> que;

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

	cin >> N >> M;
	while (N) {
		for (int i = 1; i <= N; i++) que.push(i);
		while (que.size() > 1) {
			for (int m = 1; m < M; m++) {
				que.push(que.front());
				que.pop();
			}
			que.pop();
		}

		cout << que.front() << '\n';
		que.pop();

		cin >> N >> M;
	}
}