어떤 문제인가?

요세푸스 순열을 구하는 문제.

요세푸스 순열?

다음 위키백과 내용을 참고하자.
-> https://en.m.wikipedia.org/wiki/Josephus_problem
참고로 이 문서에 있는 해답 부분에는 가장 마지막으로 살아남는 사람이 몇번째 사람인지만 알려준다. 순열을 구하는 방법을 찾기 위해서는 다음에 제거당할 사람이 몇 번째 사람인지 결정하는 알고리즘이 필요한데, 이건 큐를 이용하거나 리스트를 계속 돌려서 확인해도 무방하다.

내 풀이

일단 큐에 있는 원소를 제거하는 부분을 구현해야 한다. 크게 2가지 방법으로 풀 수 있다.

1. 정직하게 주어진 범위 내에서만 큐 원소 삽입 및 제거 실행
2. 1000보다 큰 수만큼 배열 크기를 잡고 큐 원소 삽입만 실행

나는 첫번째 방식으로 접근했다. 추후 공간복잡도에 제한이 걸릴 것을 대비해 우직하게 푸는 것으로 했다.

#include <stdio.h>
#define SIZE 1000

int Q[SIZE],f=0,r,s=0,j=0;

int main() {
    int N,K,i=0;
    scanf("%d %d",&N,&K);
    for(;i<N;i++) {
        Q[i]=i+1;
    } s=N; r=N-1;
    printf("<");
    while(s>1) {
        if(j==K-1) {
            printf("%d, ",Q[f]);
            for(i=f+1;i<s;i++) Q[i-1]=Q[i];
            s--; f%=s; r%=s; j=0;
        } else {
            f=(f+1)%s; r=(r+1)%s; j++;
        }
    }
    printf("%d>", Q[f]);
}

우아하진 않지만, 기본 개념을 체득한 것으로 만족한다.

다른 사람들의 풀이

여러 풀이가 존재한다.

1. 배열에 여태껏 제거한 수 집어넣고 확인.

#include <stdio.h>

int main() {
	int n, m, idx = 0, cnt = 0; scanf("%d %d", &n, &m);
	int t = n;
	int check[1001] = { 0 };

	printf("<");
	while (t--) {
		while (1) {
			if (!check[idx]) cnt++;
			if (cnt == m) break;
			idx++;
			idx %= n;
		}
		check[idx] = 1;
		cnt = 0;
		printf("%d", idx + 1);
		if (t) printf(", ");
	}
	puts(">");
}

durano님 풀이
-> https://www.acmicpc.net/source/21294411

2. 앞서 말했던 충분히 큰 배열에 집어넣고 출력.

#include <stdio.h>

int q[1000001];

int main()
{
	int i,st=0,ed=0,num=1,n,m;

	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
		q[++st]=i;
	printf("<");
	while(1)
	{
		ed++;
		if(num!=m)
		{
		    num++;
			q[++st]=q[ed];
		}
		else if(st!=ed)
		{
			printf("%d, ", q[ed]);
			num=1;
		}
		else
		{
		    printf("%d>",q[ed]);
		    break;
		}
		
	}

	return 0;
}

qw123rt45님 소스
-> https://www.acmicpc.net/source/11856688