[알고리즘] 백준알고리즘 1158 조세퍼스 문제

안녕하세요 감자코딩에 감자개발자입니다. 이번에 살펴볼 알고리즘 문제는 조세퍼스 문제 1158번 문제입니다.

문제 링크 1158 조세퍼스 문제 

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

조세퍼스 문제 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256 MB	13938	6986	5285	52.089%

문제

조세퍼스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 M(≤ N)이 주어진다. 이제 순서대로 M번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, M)-조세퍼스 순열이라고 한다. 예를 들어 (7, 3)-조세퍼스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 M이 주어지면 (N,M)-조세퍼스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ M ≤ N ≤ 5,000)

출력

예제와 같이 조세퍼스 순열을 출력한다.

예제 입력 1 

7 3

예제 출력 1 

<3, 6, 2, 7, 5, 1, 4>

---

위에 간략하게 문제를 확인할 수 있습니다.

여기서 가장 중요한 부분은 조세퍼스 순열에 대한 이해가 필요합니다.

위에 테스트 케이스에서 주어진 조건은 

( N = 7, M = 3)값으로 설명을 해드리겠습니다.

조세퍼스 순열이란?

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 M(≤ N)이 주어진다. 이제 순서대로 M번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다.

라고 정의 되어있습니다.

이게 무슨말인가 살펴보았더니,

1) 하나의 원 테이블에 에 여러 사람 1~N번호를 가진  사람들이 있다고 가정합시다.

2)그 N까지의 사람들중에서 M번째 순서가 되기 전까지 맨 앞에 있는 사람들은 맨뒤로 빼줍니다.

3) 이 과정을 반복하다가

4) M번째 순서가 되었을때  맨앞에 있는 값들을 제거 해줍니다. 

5) * 여기서 중요 * 제거된 값들을 다시 하나의 공간안에 저장시켜 이값들을 출력시켜주면 조세퍼스 배열의 형태로 출력이 되게 됩니다.

예를 들어서 설명해보겠습니다.

arr={1,2,3,4,5,6,7} 이라는 번호가 가진 사람들이 있습니다 ( N = 7, M = 3)값이 있다고 가정합시다.

result = { }  // 삭제하는값들을 저장하기 위한 변수라고 생각하겠습니다.

조세퍼스 원리에 따라, 

1. 처음으로 1번을 7번뒤로 옮기겠습니다. 2345671 (M = 1)
2. 2번을 1번뒤로 옮기겠습니다. 3456712 (M = 2)
3. 3. M값이 3이됨에 따라 3을 다른 메모리에 저장한다고 가정하겠습니다.
4. result = {3}이 값이 들어오고 이제 
5. arr = {4,5,6,7,1,2} 의 값이 들어오게될것입니다. 조세퍼스에서 첫번째 과정이 끝난것입니다.
6. 이제 두번째 과정을 시작해보겠습니다. 간략하게 설명하겠습니다.
7. 4 5 6 7 1 2 ->(M=1) 5 6 7 1 2 4 ->(M=2) 6 7 1 2 4 5 -> (M=3 )7 1 2 4 5 이제 여기에서 값을 저장해야 되겠지요?
8. 그러면 이제 arr = {7,1,2,4,5} 가 남아있게되고, result ={3,6이라는 값이 남아있게 됩니다.}

어떠신가요. 이상태로 계속 쭉 진행하게되면 마지막에 arr에 있던 배열에 값들이 result로 옮겨가게 되겠지요?

그 값이 조세퍼스 원리로 정리된 조세퍼스 순열입니다. 

+ 저는 여기에서 queue자료형을 사용하여 이문제를 해결하였습니다.

왜냐하면, queue를 사용해야지, 앞,뒤를 빼는 과정에 있어서 FIFO(First in First Out)의 자료형이 적합하다고 판단이 들었습니다.

---

코드 리뷰

//
//  1158(조세퍼스문제).cpp
//  Algorigm_Study
//
//  Created by kgh on 16/12/2018.
//  Copyright © 2018 kgh. All rights reserved.
//
#include <stdio.h>
#include <iostream>
#include <queue>
using namespace std;
int main(void){
    
    // N,M 입력하기 예를들어 (7,3) 일경우 1~7(N)까지의 수중에서 M번째 맨앞에 수를 제거하면서 조세퍼스 순열을 만들어준다.
    
    int N,M;
    int cnt=1;
    queue<int> q,result;
    scanf("%d %d", &N, &M);
    
    // queue에 1 ~ N 까지의 값 push
    
    for(int i=0; i<N; i++){
        q.push(cnt);
        cnt++;
    }
    printf("<");
    // N의 범위 만큼 실행시켜준다 N = 7 일경우
    for(int i=0; i<N-1; i++){
        // M의 범위 만큼 실행시켜준다 M= 3 일경우
        for(int j=0; j<M-1; j++){
            // 가장 맨앞에 있는 값들을 맨 뒤로 돌리는 과정
            q.push(q.front());
            // 그리고 맨앞에 있는 값을 pop
            q.pop();
            
        }
        // 이중포문에 안쪽포문이 끝나게 되면 맨앞에는 결국 삭제되어야하는 값이 남게됩니다.
        printf("%d, ", q.front());
        q.pop();
    }
    printf("%d>\n",q.front());
    return 0;
}

이상 백준알고리즘 조세퍼스 문제 분석 및 코드 리뷰를 마치겠습니다.

감사합니다. 이상 감자코딩에 감자개발자였습니다 :)