취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 6602번 문제인 Eeny Meeny Moo이다.
문제는 아래 링크를 확인하자.

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

사람이 원형으로 1번부터 N번까지 N명이 순서대로 앉아있고, 1번 사람부터 순서대로 사람을 세어나가기 시작해 K명마다 한 명씩 제외해나가는 것을 반복할 때 마지막으로 남는 사람의 번호를 찾는 문제를 Josephus Problem이라고 한다. 해당 문제의 풀이는 11025번 문제(링크)의 풀이글을 참고하자.

Josephus Problem의 풀이를 이용하여 문제의 조건을 만족하는 m값을 찾을 때까지 m을 하나씩 증가시키는 것을 반복해 문제를 해결하자.

위와 같은 Josephus Problem의 풀이를 모르더라도, 미리 150까지의 답을 큐 등을 이용한 시뮬레이션으로 구해두고 제출할 프로그램에는 답만을 저장해 출력하게끔 코드를 작성하여 문제를 해결할 수도 있다.

아래는 제출한 소스코드이다.

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

int ans[151];

int solve(int NN) {
	int K = 2;
	while (1) {
		int N = NN - 1;
		int ans = 0;
		for (int i = 1; i <= N; i++) {
			ans = (ans + K) % i;
		}

		if (ans == 0) return K;
		K++;
	}

	return -1;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 3; i < 151; i++) ans[i] = solve(i);

	int x; cin >> x;
	while (x) {
		cout << ans[x] << '\n';
		cin >> x;
	}
}