[백준 1158번] 요세푸스 문제 (C++)

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

1158번: 요세푸스 문제

 

이번 포스팅에서는 백준 1158번 문제를 학습합니다.

 

문제

요세푸스 문제는 다음과 같다.

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

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

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

출력

예제와 같이 요세푸스 순열을 출력한다.

 

 

I)문제이해

 (7, 3) 요세푸스 순열을 예로 들어 이해해보자. 1번부터 7번까지 7명의 사람이 원을 이루면서 앉아있고, 양의 정수 3이 주어진다.

이제 순서대로 3번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다.

이 과정은 7명의 사람이 모두 제거될 때까지 계속된다.

 

이 과정을 원을 이루면서 앉아 있는 그림으로 이해해보면 아래 그림과 같다. 

 

 

빨간색 1,2,3은 나가는 순서이고, 노란색이 칠해진 숫자는 나간 숫자이다.

따라서 (7, 3) 요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

 

피드백

큐 파트의 문제를 풀고 있어서 어떻게든 큐로 풀어야겠다 하고 접근했다.  (언젠가 이 문제를 다시 만날 때 큐를 바로 떠올리길!!!!)

K에 해당하지 않는 수는 뒤로 보낸 후(새로 집어넣은 후), 원래 맨 앞에 있는 수는 제거하는 방식이다.

 

#include <iostream>
#include <queue>
using namespace std;

int main(){
    int N;
    cin>> N;
    int K;
    cin>>K;
    queue<int> q;
    
    for(int i=0;i<N;i++){
        q.push(i+1);
    }
    
    cout<<"<";
    
    while(N--){
        
        for(int p =0; p< K-1;p++){
            q.push(q.front());
            q.pop();
        }
        
        cout<<q.front();
        q.pop();
        
        if(N){
            cout<<", ";
        }
    }
    cout<<">";
    
    return 0;
}

코드설명

먼저 N, K를 입력받는다. 그 후, queue를 선언하여 1 부터 N 까지 순서대로 넣어준다.

N개의 수가 나와 요세푸스 순열을 이루어야 하므로 while 문을 N번 반복하고,

마지막엔 ", "가 필요하지 않으므로 if(N)으로 조건문을 만들어 준다.

for(int p =0; p< K-1;p++){
            q.push(q.front());
            q.pop();
            
        }

이 부분이 코드에 핵심이라고 할 수 있는데, K번째 수를 빼내는 것이므로 K번째 앞의 K-1, K-2 ... 숫자들은 push(front())를 통해 뒤로 보내주고, pop을 통해 제거한다.

   cout<<q.front();
        q.pop();

그 후 위 코드에서 K번째에 해당하는 수를 출력하고 제거한다.

 

 

 

 

 

 

 

 

*유의사항

- 공부 중인 인공지능공학과 대학생이 정리해서 남긴 정리입니다.

- 정확하지 않거나, 틀린 점이 있다면 댓글로 알려주시면 감사하겠습니다.