[백준] 1158: 요세푸스 문제

 

원형 연결 리스트 문제이다.

 

K번째 사람을 제거하고 N명의 모든 사람이 제거될 때까지 반복해야 한다.

 

 

 

입출력 예시다.

 

 

 

// 원형 연결리스트 문제
// 제거되는 순서 출력
#include<stdio.h>

int main() {
    int N;
    int K; 
    int check[5001] = {0, }; 
    int flag;

    scanf("%d %d", &N, &K);

    flag = K;

    printf("<%d", flag);

    // 제거된 노드는 1로 표시
    check[flag] = 1;

    // N개의 번호가 모두 제거될 때까지 반복
    for(int i=0; i<N-1; i++) {
        // K개의 번호를 지나가도록 반복
        for(int j=0; j<K; j++) {
            while(1) {
                flag++;
                // N보다 커지면 1로 고정
                if(flag > N) flag = 1;
                // 현재 위치의 노드가 제거되었는지 확인
                // 제거되지 않았으면 break
                if(!check[flag]) break;
            }
        }
        // 제거된 노드 출력
        printf(", %d", flag);
        // 제거 표시
        check[flag] = 1;
    }
    printf(">");
}

 

사람 수, 제거 순서는 각각 N, K에 입력받는다.

 

check 배열과 flag로 N개의 번호가 모두 지워졌는지 확인할 것이다.

 

바깥쪽의 for문은 전체 노드의 개수에 따라 반복하고

 

안쪽의 for문은 제거되는 순서 K에 따라 현재 위치 flag를 이동시킨다.

 

중첩된 while 루프는 중복되거나 이미 제거된 노드를 건너뛰면서 적절한 위치로 이동한다.

 

이때 제거된 번호라면 배열에 1이, 제거되지 않았다면 0이 입력된다.

 

1부터 N 사이에서만 플래그 값을 검증할 수 있도록 

flag가 N보다 커지면 1로 고정한다.