[C++/28066] 타노스는 요세푸스가 밉다.

---

⛔ 단순히 기록용 입니다... 어떻게 풀었는가 생각도 다시 해보고 그러니까 아마도 도움은 안되실 것 같습니다.

---

컨베이어 벨트처럼 차례대로 정리하고 정리하지 않은 박스는 맨 뒤로 보내는 작업입니다. 링크드 리스트를 직접 구현해서 문제를 해결할 수도 있는 문제네요. 하지만, 그렇게까지 고생은 하고싶지 않기 때문에, 간단하게 배열로 해결하려고 했지만, N의 개수가 1,000,000개입니다. K가 극단적으로 적다면? (1,000,000 + 1)을 500,000번 반복해야 하기 때문에 시간 초과가 발생할 수 밖에 없습니다. 그래서 queue를 이용해 푼다면? 쉽게 풀리는 문제입니다.

아래는 정답코드입니다.

#include<iostream>
#include<cstring>
#include<queue>

#define MAX 1000100
using namespace std;

int sq,len,n,k,board[MAX],temp[MAX];
queue<int> q;

void init() {
	
	cin >> n >> k;
	
	memset(board,0,sizeof(board));
	for(int i = 0; i < n; i++){
		board[i] = i + 1;
		q.push(i+1);
	}

	len = n;
	sq = 0;

}

void solve() {

	while(q.size() > k) {
		int temp = q.front();
		q.pop();
		
		for(int i = 0; i < k - 1; i++){
			q.pop();
		}
		
		q.push(temp);
	}
	
	cout << q.front();
    
    /* 시간초과 코드
    while(len > k) {
		for(int i = 0; i < len; i++){
			temp[i] = 0;
		}
		
		for(int i = 0; i <= len - k; i++) {
			temp[i] = board[(i + k) % len];
		}

		//memcpy(board,temp,sizeof(board));
		
		

		len -= (k - 1);
		
		for(int i = 0; i < len; i++) {
			board[i] = temp[i];
		}
	}
	
	cout << board[0];
    */
		
}

int main() {
	
	init();
	solve();
	
	return 0;
}