[210317][백준/BOJ] 1158번 요세푸스 문제

문제

입출력

풀이

STL list로 문제를 해결하였다.

1부터 N까지의 숫자랑 K번째 사람을 제거하기 위한 숫자 K가 주어지며 1부터 N번의 사람이 원을 이루면서 앉아있다.

1. 시작번호가 1, 끝번호가 7이며 1부터 7까지의 사람중에 3번째 사람이 제거되었다.
   // 1 2 3 4 5 6 7
   3
2. 3번째 사람이 제거되었으며 다음 번호인 4번을 시작번호로 해서 3번째에 위치한 6번이 제거도었다.
   // 4 5 6 7 1 2
   6
3. 6번째 사람이 제거되었으며 다음 번호인 7번을 시작번호로 해서 3번째에 위치한 사람을 찾아야 하며 총 7명의 사람이 원형으로 앉아있으므로 7번 다음번호는 1번이 된다. 따라서 7번을 시작번호로 해서 3번째에 위치한 2번이 제거되었다.
   // 7 1 2 4 5
   2
4. 이를 반복하면 7, 5, 1, 4번이 제거된다.
   // 4 5 7 1
   7
   // 1 4 5
   5
   // 1 4
   1
   // 4
   4
5. 구현을 할때 주의할만한 점은 n명의 사람이 원형으로 앉아있으므로 커서가 list의 end에 도달하면 커서를 list의 begin으로 보내주면 된다.

if (t == L.end())
    t = L.begin();

6. 남아있는 사람이 k보다 작을경우를 위해서 위에서 구현한 코드를 t++; 이후에 한번 더 적어주면 된다.

코드

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n, m, cnt = 0;
	list<int>L;
	scanf("%d%d", &m, &n);
	for (int i = 1; i <= m; ++i)
		L.push_back(i);
	list<int>::iterator t = L.begin();

	for (int i = 0; i < m; ++i)
	{
		for (int k = 0; k < n - 1; ++k)
		{
			if (t == L.end())
				t = L.begin();
			t++;
			if (t == L.end())
				t = L.begin();
		}
		cnt++;
		if(cnt==1) cout << "<";
		cout << *t;
		if (cnt < m) cout << ", ";
		else cout << ">";
		t = L.erase(t);
	}

// 1 2 3 4 5 6 7  3
// 4 5 6 7 1 2	  6
// 7 1 2 4 5      2
// 4 5 7 1        7
// 1 4 5          5           
// 1 4            1
// 4              4

}