1158) 요세푸스 문제

문제 ) www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

 

풀이 ) 

이번 문제는 연결리스트를 활용하는 대표적인 문제이다.
c++ STL list 는 양방향 연결 리스트인데, 이걸 응용해서 원형 연결 리스트로 바꿔서 사용했다.

리스트를 선언한 뒤, push_back 을 이용해서 1~n 번까지 list에 넣어 준다.
이터레이터를 만들어서 리스트의 begin()을 가리키케 만든다.

n번째에 있는 사람부터 제거한다고 했으니, 이터레이터를 움직이면서 1명이 남을 때까지 제거할 번호를 찾는다.

원형 연결 리스트로 만들기 위해 erase 를 한 뒤, del = li.end() 와 같다면 다시 li.begin()으로 옮겨준다.

K 번째 있는 사람을 제거하기 위해서는 K-1만큼 이터레이터를 옮기면 된다.
예를들어, 문제에서 처럼 K=3 으로 생각을하고 3번째 사람을 제거한다고 생각하면

1 -- 2 -- 3  이런 식으로 사람이 있을텐데, 이미 이터레이터가 1을 가리키고 있으므로 세번째에 있는 3번을 제거하려면 2칸만 이동하면 되기 때문이다.

이렇게 반복을 하다가 혼자 남게되면 혼자 남은 사람의 번호를 출력하고 break로 바로 반복문을 빠져나온다.

 

코드 )

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

int N, K;
list<int> li;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> N >> K;
	
	for (int i=1; i<=N; i++)
		li.push_back(i);
	
    list<int>::iterator del = li.begin();
	
    for (int i=1; i<K; i++)
		del++;
	cout << '<';
    
	while (N > 0) {
		if (N == 1) {
			cout << *del;
			break;
		}
		cout << *del << ", ";

		del = li.erase(del);
		if (del == li.end()) del = li.begin();
		N--;
		for (int i=1; i < K; i++) {
			del++;
			if (del == li.end()) del = li.begin();
		}
	}
	cout << '>';
}