글 읽기 - C) 1158 조세퍼스 문제 부탁드립니다

qorwngus0729 4년 전 0

일단 큐를 이용하였습니다

반례를 찾아봤는데 문제점을 못찾겠네요...

제가 못찾은 반례가 있거나 코드에 문제가 있는것 같은데

해결방안 제시해주면 정말 감사드리겠습니다!

#include<stdio.h>
#include<string.h>

typedef struct queue {
	int people[5001];
	int front, back;
}Queue;

void ClearQueue(Queue* pqueue)
{
	memset(pqueue->people, NULL, sizeof(pqueue->people));
	pqueue->front = 1;
	pqueue->back = 0;
}

void Put(Queue* pqueue, int data)
{
	if (pqueue->back == 5000)
		return;
	else
	{
		pqueue->back++;
		pqueue->people[pqueue->back] = data;
	}
}

int Get(Queue* pqueue)
{
	int get_data;

	if (pqueue->back == 0)
		return NULL;
	else
	{
		get_data = pqueue->people[pqueue->front];
		pqueue->people[pqueue->front] = NULL;
		memmove(pqueue->people, pqueue->people + 1, sizeof(pqueue->people) - sizeof(int));
		pqueue->back--;
		return get_data;
	}
}

int main()
{
	Queue queue,temp_queue;
	int Josephus[5000] , index = 0;
	int people_num, delete_num;

	ClearQueue(&queue);
	ClearQueue(&temp_queue);

	scanf("%d %d", &people_num, &delete_num);

	for (int i = 1; i <= people_num; i++)
		Put(&queue, i);

	while(1)
	{
		for (int j = 1; j <= delete_num; j++)
		{
			if (j == delete_num)
			{
				Josephus[index] = Get(&queue);
				index++;
			}
			else
				Put(&queue,Get(&queue));
		}
		if (queue.back < delete_num)
		{
			for (int k = 1; k < delete_num; k++)
			{
				Josephus[index] = Get(&queue);
				index++;
			}
			break;
		}
	}

	printf("<");
	for (int i = 0; i <index; i++)
		if(i==index-1)
			printf("%d>\n", Josephus[i]);
		else
			printf("%d, ", Josephus[i]);	
	
	return 0;	
}

djm03178 4년 전 1

5 4

답은 4 3 5 2 1인데 4 3 5 1 2가 출력됩니다.

qorwngus0729 4년 전 0

답변 감사합니다

저가 문제 개념을 잘못 이해한건지..

제가 이해한 조세퍼스에 따르면 (5,4) 의 답이 4 3 5 1 2 가 나오는데

혹시 그러면 (6,5)의 답이 5 4 6 1 2 3 도 아닌건가요..?

djm03178 4년 전 2

5 4는 다음과 같이 됩니다.

1 2 3 4 5 에서 4번째 1 2 3 4

5 1 2 3에서 4번째 5 1 2 3

5 1 2에서 4번째 5 1 2 5

1 2에서 4번째 1 2 1 2

1에서 4번째 1 1 1 1

6 5는 5 4 6 2 3 1입니다.

qorwngus0729 4년 전 0

이해를 잘못했었네요..ㅠ

덕분에 해결했습니다! 친절한 설명 감사합니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

C) 1158 조세퍼스 문제 부탁드립니다

qorwngus0729 4년 전 0

djm03178 4년 전 1

qorwngus0729 4년 전 0

djm03178 4년 전 2

qorwngus0729 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말