1158: 요세푸스 문제

자료구조

실버 4

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

1158번: 요세푸스 문제

 

-결과

 

-코드

#include<stdio.h>

int main() {
    int N, K, check[5002] = {0, }, cur;
    scanf("%d %d", &N, &K);
    cur = K;
    printf("<%d", cur);
    check[cur] = 1;
    for(int i=0; i<N-1; i++) {
        for(int j=0; j<K; j++) {
            while(1) {
                cur++;
                if (cur > N) {
                    cur = 1;
                }
                if (!check[cur]) {
                    break;
                }
            }
        }
        printf(", %d", cur);
        check[cur] = 1;
    }
    printf(">");
}

 

-풀이

k번째 사람을 제거한 후 제거되는 사람의 순서를 출력하면 되기 때문에

먼저 번호를 k로 고정해야 한다.

먼저 for문으로 n개의 번호가 제거될 때까지 반복되게 한다.

그 이후 다시 안쪽에 for문을 이용하여 k개의 번호를 지나면 제거하도록 반복문을 작성한다.

미리 선언한 변수와 배열을 이용하여 번호의 제거를 확인한 후에 번호를 출력하도록 작성한다.