c언어 11866번 요세푸스 문제 0 (백준)

#include <stdio.h>

int main(void)
{
	int n, k, i; //몇 개, k번, index변수
	scanf("%d%d", &n, &k);
	int a[n+1]; //배열 만들기
	for(i = 1; i<=n; i++) a[i]=1; //요소들에 1을 대입
	
	printf("<");
	i=1; //1부터 시작
	int count = 0; //N번 다 제거 되면 종료
	int count_k = 0; //k번째마다 수를 제거
	while(1)
	{
		if(a[i] == 1) count_k++; //몇 번째 인지를 계산하는 코드
		if(a[i] == 1 && count_k == k) {//k번째 일 때의 수를 제거
			count_k = 0;
			a[i] = 0;
			count++;
			if(count == n) { //다 제거시 while 종료
				printf("%d>", i);
				break;
			}
			printf("%d, ", i); //제거된 수 출력
		}
		i++;
		if(i>n) i = i-n;
	}
    return 0;
}

 

풀이

 

ex) 7 3

 

배열 1 2 3 4 5 6 7

->     1 2 3 제거 4 5 6 7

->     4 5 6 제거 7 1 2

->     7 1 2 제거 4 5 

->     4 5 7 제거 1 

->     1 4 5 제거

->     1 -> 4 -> 1 제거

->     4 -> 4 -> 4 제거

 

순서 3 6 2 7 5 1 4

 

1) 초기값을 1로 하고, 지워지면  0으로 한다.

값이 1인 배열이 k번 있을 때, 그 배열의 값을 0으로 바꾸고 출력한다.

2) 수를 하나씩 제거하다가, 다 제거하면 프로그램을 종료한다.

 

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

11866번: 요세푸스 문제 0