72. 공주구하기[조세퍼스 Queue 이용]

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다.

문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅

 

 

입력예제 1

8 3

 

출력예제 1

7

 

풀이 

- k라는 수를 외친 왕자가 나간다

- 가장 문제가 되는 건 큐는 선입선출인데 3번째 왕자를 뺄 때 1,2번 왕자를 다시 넣어줘야 하는 점이다.

- for문이 돌면서 1,2번을 큐의 뒤쪽에 넣어준 후 pop으로 빼준다

- 3번이 되면 뒤에 넣지 않고 그냥 pop으로 빼준다

- Q의 사이즈가 1이 되면 정답이므로 출력한다 => 출력후 pop하면 Q.empty()가 되어 끝나게 된다.

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

//72. 공주구하기 (조세퍼스 : 큐를 이용하는 방법)
int main(){
    queue<int> Q;
    int n, k, i;
    scanf("%d %d", &n, &k); //왕자수, k번호
    for(i=1;i<=n;i++){
        Q.push(i);
    }
    while(!Q.empty()){
        for(i=1;i<k;i++){
            Q.push(Q.front()); //가장 앞의 값 가장뒤에 push
            Q.pop(); //뒤에 넣은 후에 pop함
        }
        Q.pop(); //3외친 사람 pop함
        if(Q.size()==1){
            printf("%d\n", Q.front());
            Q.pop();
        }
    }
    return 0;
}