(c++)백준 1168번: 요세푸스 문제 2

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

1168번: 요세푸스 문제 2

[풀이]

이 문제는 이전의 요세푸스 문제와 같이 링크드 리스트로 풀면 시간초과가 난다. (∵매 회 포인터가 K-1번 움직임)

따라서 vector와 moduler를 사용하여 그때그때 K번째 번호를 출력하고 벡터에서 지워주는 방식으로 풀었다. 

 

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

int N, K;
vector<int>v;//남은 사람들

void input() {
	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		v.push_back(i);
	}
}

void solution() {
	input();
	int curNum = -1;

	cout << '<';
	for(int n = N; n > 0; n--) {
		curNum = (curNum + K) % n;

		cout << v[curNum];
		if (n == 1) 
			cout << '>'; 
		else 
			cout << ", ";

		v.erase(v.begin() + curNum);
		curNum--;
	}
}

int main() {
	solution();
	return 0;
}