BOJ 11866, 1158 : 요세푸스 문제 0, 요세푸스 문제

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/11866

www.acmicpc.net/problem/1158

 

참고

- BOJ 10845, 18258 : 큐, 큐2

- BOJ 1168 : 요세푸스 문제 2

 

 

요세푸스 문제 0은 요세푸스 문제보다 K, N 값만 다르다. 

MAX 값을 5000이상으로 잡으면 두 문제 모두 풀 수 있다.

 

큐 기본 문제를 풀면 큐의 구현은 아래와 같다.

 

큐의 크기   :  wp - rp

큐의 pop   :  queue[rp++]

큐의 push :  queue[wp++]

 

먼저 사람들을 큐의 순서대로 넣는다. 예제의 경우는 

1 2 3 4 5 6 7 이 큐에 들어간다.

 

K 번째 사람을 제거하기 위해 K - 1번 pop하고 다시 push한다. 이 경우는 K = 3 - 1 = 2번 반복한다.

그리고 마지막 K = 3번째는 pop만 한다. (출력)

 

2 3 4 5 6 7 1  (1 pop, 1 push)

3 4 5 6 7 1 2  (2 pop, 2 push)

 

3번 삭제(pop) → 4 5 6 7 1 2

 

다시 K번째 사람을 제거하기 위해 pop하고 다시 push를 2번 한다.

그리고 pop(출력)한다.

 

5 6 7 1 2 4  (4 pop, 4 push)

6 7 1 2 4 5  (5 pop, 5 push)

 

6번 삭제(pop) → 7 1 2 4 5

 

다시 2번 반복 한다. 그리고 pop(출력)한다.

 

1 2 4 5 7  (7 pop, 7 push)

2 4 5 7 1  (1 pop, 1 push)

 

2번 삭제(pop) → 4 5 7 1

 

계속 해서 반복하면

3번, 6번, 2번, 7번, 5번, 1번, 4번 순으로 삭제된다. → <3, 6, 2, 7, 5, 1, 4>

 

최대 5000명이 5000번 push와 pop이 이루어지므로 queue의 크기는 MAX * MAX로 잡는다.

#include <stdio.h>

#define MAX (5000 + 100)

int N, K;
int queue[MAX * MAX];
int wp, rp;

int main(void)
{
	scanf("%d %d", &N, &K);

	for (int i = 1; i <= N; i++) queue[wp++] = i;

	printf("<");

	while (wp - rp - 1)
	{
		for (int i = 0; i < K - 1; i++) queue[wp++] = queue[rp++];
	
		printf("%d, ", queue[rp++]);
	}

	for (int i = 0; i < K - 1; i++) queue[wp++] = queue[rp++];

	printf("%d>\n", queue[rp++]);

	return 0;
}

숫자의 출력은 "숫자," 지만 마지막은 "숫자>" 이므로 queue의 size가 0이 되기 바로 전까지만 반복(wp - rp - 1)하고, 

">"로 출력을 하기 위해 남은 한번은 마지막에 실행한다.