1/27 [C] 백준 1158번 - 요세푸스 문제

<문제>

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

1158번: 요세푸스 문제

 

<내가 제출한 코드>

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main() {
	int n, k, i,j, cnt;
	int a[5002] = { 0 };

	scanf("%d %d", &n, &k);
	printf("<%d",k);
	a[k] = 1;
	cnt = k;
	for (i = 0; i < n-1; i++) {
		for (j = 0; j < k; j++) {
			while (1) {
				cnt++;
				if (cnt > n) cnt = 1;
				if (a[cnt] == 0) break;
			}
		}
		printf(", %d", cnt);
		a[cnt] = 1;
	}
	printf(">");


	
}

요세푸스 순열을 어떻게 구현하느냐에 대해서 시간을 많이 쏟았음.

 

현재 위치를 알려주는 변수 cnt를 선언해줌.

일단 제일 처음의 변수(k)는 먼저 출력해주고, 다른 변수들을 출력해줌. (혹은 다른 변수들을 출력하고 제일 나중의 변수를 출력해주는 방법도 있으나 전자의 방법이 더 구현이 쉬울것 같아서 전자의 방법 선택함.)

이중 반복문을 만들어 주었음. 겉에 for문은 나머지 n-1개의 변수를 출력해주는 반복문, 안쪽 for문은 k만큼 이동하기 위한 for문임.

그 안에 while문이 있는데 이건 만약 1이면 (이미 출력된 변수면) while문이 계속 돌아가기 때문에 cnt를 계속 증가시킴으로써 변수들을 건너뛰고, 0이면 while문이 멈춰서 현재있는 위치를 고정시키는 역할임. (만약 현재 위치가 n을 벗어났다면 다시 1로 돌아가게 하는 역할도 있음)

안쪽 for문이 총 k번만큼 돌아가기 때문에 0으로 표시되어 있는 변수를 k번 세고 표시된 현재 위치 cnt를 출력해줌.

 

그리고 마지막으로 > 를 출력해주면 끝

 

..

...

..

진짜 어려웠다 근데 진짜 간단히 생각하면 빨리 풀리는 문제인듯.