공주 구하기(요세푸스 문제) / c / 제한시간 없음

▣ 문제

- 정보 왕국의 이웃 나라 외동딸 공주가 숲속의 괴물에게 잡혀갔습니다. 정보 왕국에는 왕자가 N명이 있는데 서로 공주를 구하러 가겠다고 합니다. 정보왕국의 왕은 다음과 같은 방법으로 공주를 구하러 갈 왕자를 결정하기로 했습니다. 왕은 왕자들을 나이 순으로 1번부터 N번까지 차례로 번호를 매긴다. 그리고 1번 왕자부터 N 번 왕자까지 순서대로 시계 방향으로 돌아가며 동그랗게 앉게 한다. 그리고 1번 왕자부터 시 계방향으로 돌아가며 1부터 시작하여 번호를 외치게 한다. 한 왕자가 K(특정숫자)를 외치면 그 왕자는 공주를 구하러 가는데서 제외되고 원 밖으로 나오게 된다. 그리고 다음 왕자부터 다시 1부터 시작하여 번호를 외친다. 이렇게 해서 마지막까지 남은 왕자가 공주를 구하러 갈 수 있다.

예를 들어 총 8명의 왕자가 있고, 3을 외친 왕자가 제외된다고 하자. 처음에는 3번 왕자가 3 을 외쳐 제외된다. 이어 6, 1, 5, 2, 8, 4번 왕자가 차례대로 제외되고 마지막까지 남게 된 7 번 왕자에게 공주를 구하러갑니다. N과 K가 주어질 때 공주를 구하러 갈 왕자의 번호를 출력하는 프로그램을 작성하시오.

 

▣ 입력설명

- 첫 줄에 자연수 N(5<=N<=1,000)과 K(2<=K<=9)가 주어진다.

 

▣ 출력설명

- 첫 줄에 마지막 남은 왕자의 번호를 출력합니다.

 

<내 코드>

#pragma warning(disable:4996)
#include<stdio.h>

int prince[1001] = { 0 };
int ans;
int n;
int check(int a) {
	int i;
	a = n;
	for (i = 1; i <= n; i++) {
		if (prince[i] == 0) a--;
		else ans = prince[i];
	}
	if (a == 0) return 1;
	else return 0;
}

int main() {
	int k;
	int i;
	int cnt = 1;
	scanf("%d %d", &n, &k);
	for (i = 1; i <= n; i++) prince[i] = i;

	while (1) {
		for (i = 1; i <= n; i++) {
			if (prince[i] == i && cnt % k == 0) {
				prince[i] = 0;
				cnt = 1;
			}
			else if (prince[i] == i) cnt++;
		}
		if (check(n)) break;
	}
	printf("%d\n", ans);
	return 0;
}

내 코드의 접근 방법은 일단 prince라는 배열을 만들어서 각 index에 N명의 왕자를 넣었다.

 

그리고 while문을 통해서 k번째마다 왕자를 배열에서 제외 시켰다. 이때 필요한 변수는 cnt이다.

 

for문을 돌면서 왕자가 아직 빠지지 않고 k번째가 아니라면 cnt++을 하고 k번째 일때 왕자를 빼주고 cnt를 다시 1로 초기화 시켜주었다.

 

마지막으로 check 함수에서는 prince 배열에서 단 한명의 왕자만 남아있다면 1을 반환시켜주었다.

 

<수정한 코드>

#pragma warning(disable:4996)
#include<stdio.h>

int main() {
	int prince[1001] = { 0 };
	int n, k, i;
	int bp = 0;
	int cnt = 1;
	scanf("%d %d", &n, &k);
	for (i = 1; i <= n; i++) prince[i] = i;

	while (1) {
		for (i = 1; i <= n; i++) {
			if (prince[i] == i && cnt % k == 0) {
				prince[i] = 0;
				cnt = 1;
				bp++;
			}
			else if (prince[i] == i) cnt++;
		}
		if (bp == n -1) break;
	}

	for (i = 1; i <= n; i++) {
		if (prince[i] != 0) {
			printf("%d\n", prince[i]);
			break;
		}
	}

	return 0;
}

check라는 함수가 따로 필요없이 bp(breaking point)를 만들어서 한명만 남을때까지 while문을 반복한다.

 

마지막에 0이 아닐때 출력을 하는것으로 바꿔주었다.

 

.

 

예전에 백준에서도 비슷한 문제가 있었는데 그때는 '큐'의 개념을 활용해서 풀었다. 나중에 백준 문제도 다시 한번 풀어볼것

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