1158)조세퍼스 문제

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

문제를 읽고 떠오르는 대로 풀어내는 습관을 고칠 필요가 있을 듯하다.

아니면 풀이를 생각한 후 더 빠른 방법은 없을까 고민해보거나

채점 현황을 보니 C언어 중에서 메모리가 꽤 크고 속도가 빠른 풀이는 자료 구조를 사용한 것 같고

메모리가 작고 속도가 느린 풀이는 나랑 비슷하게 푼 것같다.

메모리가 작고 속도도 빠른 풀이도 있었다.

처음 이 문제를 풀었을 때 %연산만 잘 사용하면 될 것이라 생각했다.

예를들어 수열 1~7에서 m = 3인 조세퍼스 수열을 만드는 경우를 생각해보자.

1 2 3 4 5 6 7에서 첫 항부터 count를 하나씩 증가시키며 각 항에 접근한다.

count = 1일때 1에 접근하고, count = 2일때 2에 접근하고 , count = 3일때 3에 접근한다.

count = 3이므로 3을 조세퍼스 수열의 첫 항에 저장하고 3이 있던 항에 FALSE를 저장한다.

1 2 3 F 4 5 6 7에서 4부터 출발해 count를 다시 증가시킨다. count = 3일 때 6에 접근한다.

위 과정을 수행하면 1 2 3 F 4 5 F 7가 된다. 다시 7부터 count를 증가시키고 count = 3일 때 2에 접근 후 위 과정을 반복한다.

자 위 과정의 모양새의 핵심은 수열에 접근하는 방법인데 수열에 순환하면서 접근하기 위해 t = (t+1)%n로 인덱스를 증가시킨다.

생각을 그대로 따라가며 풀었기 때문에 간단하지만 수열에 하나하나 접근해야 하기 때문에 속도가 느리다.

#include<stdio.h>
#define FALSE 0
 
int main() {
    int n, m;
    int *seq, t = 0;
    int *josephus, q = 0;
    int count = 0;
 
    scanf("%d %d",&n,&m);
    seq = (int *)malloc(sizeof(int)*n);
    josephus = (int *)malloc(sizeof(int)*n);
    for (int i = 0; i < n;i++) {
        seq[i] = i+1;
    }
 
    while (q < n) {
        if(seq[t]!=FALSE) count++;
    
        if (count == m) {
            count = 0;
            josephus[q++] = seq[t];
            seq[t] = FALSE;
        }
 
        t = (t+1)%n;
    }
 
    printf("<");
    for (int i = 0; i < q;i++) {
        if(i<q-1)    printf("%d, ",josephus[i]);
        else printf("%d>\n", josephus[i]);
    }
 
    return 0;
}