[백준 1158] 조세퍼스 문제

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

1158번: 조세퍼스 문제

 

요구사항

1. 리스트 구현

https://na982.tistory.com/

를 참조하여 구현하였다.

2. 조건 구현

 전체의 순서를 저장한 cnt와 현재 index부터 k번째까지의 숫자 index를 나타내는 nowcnt를 이용하여 구현

 

 

#include <stdio.h>
#include <algorithm>
#include <list>
#include <iostream>


using namespace std;

struct NODE {
	int val;
	int prev;
	int next;
	int flag;
};
const int Node_size = 5000;

struct MY_LIST {
	int HEAD = Node_size;
	int TAIL = Node_size + 1;
	int pos;
	int size = 0;
	NODE node[Node_size + 2];

	MY_LIST(){
		pos = 0;
		node[HEAD].next = TAIL;
		node[TAIL].prev = HEAD;
	}
	void push_back(int data)
	{
		int prev = node[TAIL].prev;
		int next = node[prev].next; //tail

		node[pos].val = data;

		node[pos].prev = prev;
		node[prev].next = pos;

		node[pos].next = next;
		node[next].prev = pos;
		pos++;
		size++;



	}
	void push_front(int data)
	{
		int next = node[HEAD].next;
		int prev = node[next].prev; 
		

		node[pos].val = data;

		node[pos].prev = prev;
		node[prev].next = pos;

		node[pos].next = next;
		node[next].prev = pos;
		pos++;
		size++;
	}

	void insert(int p, int data)
	{
		int next = node[HEAD].next;
		for (int i = 0; i < p; i++)
		{
			next = node[next].next;
		}
		int prev = node[next].prev;


		node[pos].val = data;

		node[pos].prev = prev;
		node[prev].next = pos;

		node[pos].next = next;
		node[next].prev = pos;
		pos++;
		size++;
	}

	void pop_back()
	{
		int target = node[TAIL].prev;

		int prev = node[target].prev;
		int next = node[target].next;

		node[prev].next = next;
		node[next].prev = prev;
		size--;
	}
	void pop_front()
	{
		int target = node[HEAD].next;

		int prev = node[target].prev;
		int next = node[target].next;

		node[prev].next = next;
		node[next].prev = prev; 
		size--;
	}
	int erase(int p)
	{
		int target = node[HEAD].next;
		for (int i = 0; i < p; i++)
		{
			target = node[target].next;
		}

		int prev = node[target].prev;
		int next = node[target].next;

		node[prev].next = next;
		node[next].prev = prev;
		size--;
		return node[target].val;
	}
	int at(int p)
	{
		int target = node[HEAD].next;
		for (int i = 0; i < p; i++)
		{
			target = node[target].next;
		}
		return node[target].val;
	}
};

MY_LIST my_list;
MY_LIST ans;
int n, m;
void solve()
{
	int k = m - 1;
	int cnt = 0;
	int nowcnt = 0;
	while (true)
	{
		//cout << cnt << " " << my_list.size << " " << my_list.at(cnt) << endl;
		if (cnt >= my_list.size)
			cnt = 0;
		if (my_list.size == 0)
			return;
		if (nowcnt == k){
			int s = my_list.erase(cnt);
		//	cout << "get" << s << endl;
			ans.push_back(s);
			nowcnt = 0;
			continue;
		}

		cnt++;
		nowcnt++;
		if (cnt >= my_list.size)
			cnt = 0;
		
	}
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		my_list.push_back(i);
	solve();
	printf("<");
	for (int i = 0; i < ans.pos; i++)
	{
		if(i==ans.pos-1)
			printf("%d", ans.at(i));
		else
		printf("%d, ", ans.at(i));
	}
	printf(">");
}