취미로 코딩하기

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

이번에 볼 문제는 백준 28066번 문제인 타노스는 요세푸스가 밉다이다.
문제는 아래 링크를 확인하자.

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

문제에서 주어지는 내용을 직접 시뮬레이션하는 코드를 작성하자. 큐(queue) 자료구조에 1부터 N까지의 청설모를 차례대로 넣고, 이번 과정에서 다룰 K마리를 큐에서 접근하면 주어진 내용을 빠르게 시뮬레이션할 수 있다.

구체적으로, 큐의 첫 번째 원소가 "첫 번째 청설모"일 때, 첫 번째 청설모를 저장한 다음 큐에서 K마리(남은 청설모가 K보다 적다면 남은 마릿수)만큼 큐에서 청설모를 제거하고 첫 번째 청설모를 큐에 새로 추가하면 다음 "첫 번째 청설모"가 큐의 맨 앞에 있는 상태로 만들 수 있다. 이를 반복해 문제를 해결하자.

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

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

int N, K;
queue<int> que;

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

	cin >> N >> K;
	for (int i = 1; i <= N; i++) que.push(i);

	while (que.size() > 1) {
		int kp = que.front();
		int itercnt = min(K, (int)que.size());
		for (int i = 0; i < itercnt; i++) que.pop();
		que.push(kp);
	}

	cout << que.front();
}