[백준] 11866 요세푸스 문제 0 C

1. 문제

N명의 사람이 원을 이루면서 앉아있고, 순서대로 K번째 사람을 제거한다
원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다 
(N, K)-요세푸스 순열을 구하는 프로그램 작성하기 

2. 제한

시간 제한 2초, 메모리 제한 512MB
1 <= K <= N <= 1,000 

 

3. 알고리즘 분류

* 구현

* 자료 구조

* 큐

 

4. 접근 방식 

원을 이루는 형태라고 해서 처음에는 원형큐를 이용해서 접근해 보려고 했었는데

생각처럼 구현이 쉽지 않아서 결국 포인터 배열을 이용해서 풀었다 

다음에 풀 때는 원형큐나 Linked List, 아니면 파이썬으로 덱을 이용해서 풀어봐야지 

 

그리고 제거할 사람을 구하는 인덱스를 계산하는 방식을 찾는데 애를 좀 먹었다 

5. 전체 코드

// https://www.acmicpc.net/problem/11866
// N명의 사람이 앉아있고 순서대로 k번째 사람을 제거한다
// 한 사람이 제거되면 남은 사람들도 이루어진 원을 따라
// N명의 사람들이 모두 제거될 때까지 과정을 반복한다

// 배열을 선언해서 번호를 매기고 people[i] = i+1
// 현재 위치 index 에서 k-1 만큼 이동해서 그 사람 제거
// 현재 위치 이후의 사람들을 한 칸씩 앞으로 당기기

#include <stdio.h>
#include <stdlib.h>

int main()
{
    // n 사람 수, k 제거할 순서, i for문
    int n, k, i;

    scanf("%d %d", &n, &k);

    // 사람들을 저장할 배열
    int *people = (int *)malloc(sizeof(int) * n);
    for (i = 0; i < n; i++)
    { // 1번부터 번호 매기기
        people[i] = i + 1;
    }

    int index = 0;  // 현재 제거할 사람의 인덱스
    int remain = n; // 남은 사람 수 n명

    printf("<");

    while (remain > 0) // 사람들이 0이 될 때까지
    {                  // k번째 사람을 찾기 위해 현재 인덱스에서 k-1 만큼 이동
        index = (index + k - 1) % remain;
        printf("%d", people[index]);

        // 현재 위치 이후의 사람을 한 칸씩 당기고
        // 마지막에 중복된 사람 이전까지만 저장 (remain-1)
        for (i = index; i < remain - 1; i++)
        {

            people[i] = people[i + 1];
        }

        // 남은 사람이 1명 이상이면 , 출력
        if (remain > 1)
            printf(", ");

        remain--; // 남은 사람 수 감소
    }

    printf(">\n");

    free(people);
    return 0;
}