12. 요세푸스 문제 (Josephus Problem)

요세푸스 문제

  # 문제에 대한 자세한 개요는 검색해보는 것을 추천.

  # 대충 요약하면 41명의 사람에 대해서 3명당 한명씩 죽이는 걸 반복했을 때, 마지막 한명이 되어 살아남으려면 몇번째 자리에 있어야 하는가? 라는 문제.

  # 점화식을 이용한 수학적 풀이와 이진법을 이용한 풀이도 있지만 이 포스팅에서는 생략했다. 이쪽이 궁금하면 검색해보는 것을 추천.

  # 프로그래밍적으로는 원형 리스트를 이용해서 푸는 문제라서 이 시점에서 풀어보았다.

  # 구현한 것은 max명의 사람에 대해서 die명당 한명씩 죽일때 live명의 생존자를 보여준다. 

  # die가 0이면 첫번째 사람부터 차례대로 죽는 경우가 되고, die가 1이면 첫번째 사람 다음 사람부터 차례대로 죽는 경우가 된다.

  # 1명이상 건너뛰는 경우는 2이상 입력했을 때이다. die에 max보다 큰 수를 입력해도 잘 작동한다.

solution.h

#pragma once
#include <iostream>

class CircularList
{
	struct node
	{
		int id;
		bool exist;
	};

	node* capacity;
	int iIndex;

	int iSize;
	int iCount;

private:
	int next(int d);

public:
	void LastN(int live, int die);

public:
	CircularList(int size);
	virtual ~CircularList();
};

CircularList::CircularList(int size)
{
	capacity = new node[size];
	iIndex = 0;

	iSize = iCount = size;

	for (int i = 0; i < size; i++) {
		capacity[i].id = i + 1;
		capacity[i].exist = true;
	}
}

int CircularList::next(int d)
{
	iIndex += d;
	iIndex %= iSize;

	while (!capacity[iIndex].exist) {
		iIndex += 1;
		if (iIndex == iSize) {
			iIndex = 0;
		}
	}

	return iIndex;
}

void CircularList::LastN(int live, int die)
{
	while (iCount != live) {
		capacity[next(die)].exist = false;
		iCount--;
	}

	printf("생존자 %d명\n", live);
	for (int i = 0; i < iSize; i++) {
		if (capacity[i].exist) {
			printf("%d번 ", capacity[i].id);
		}
	}
}

CircularList::~CircularList()
{
	delete[] capacity;
}

problem.cpp

#include "solution.h"

int main() {

	int max = 0;
	while (true) {
		std::cout << "총 인원이 몇명인지 입력하세요.\n";
		std::cin >> max;
		if (max <= 0) {
			getc(stdin);
			std::cout << "이미 다 죽었습니까?\n";
			std::cin >> max;
		}
		else {
			break;
		}
	}

	CircularList solution(max);

	int live = 0;
	while (true) {
		std::cout << "살아남은 인원이 몇명인지 입력하세요.\n";
		std::cin >> live;
		if (live <= 0) {
			getc(stdin);
			std::cout << "아무리 그래도 1명이상 살려줍시다. \n";
			std::cin >> live;
		}
		else if (live > max) {
			getc(stdin);
			std::cout << "그만큼의 인원이 없습니다. \n";
			std::cin >> live;
		}
		else {
			break;
		}
	}


	int die = 0;
	std::cout << "몇 명 마다 죽일지 정하세요.\n";
	std::cin >> die;

	solution.LastN(live, die);

}