[백준/C++] 카드1

2161번: 카드1 (acmicpc.net)

2161번: 카드1

문제유형

*큐

문제

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 

그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 

여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 버린 카드들은 순서대로 1 3 2가 되고, 남는 카드는 4가 된다.

N이 주어졌을 때, 버린 카드들을 순서대로 출력하고, 마지막에 남게 되는 카드를 출력하는 프로그램을 작성하시오.

입출력 예제

 

(입력 1)	7
(출력 1)	1 3 5 7 4 2 6

풀이

1. 먼저 N을 입력받은 뒤, 큐에 순서대로 1부터 N까지의 수를 집어 넣는다.

2. 맨 위에 있는 카드를 버린 후, 그 다음 위에 있는 카드를 제일 아래에 있는 카드 밑으로 다시 보내야한다. 따라서, 버리는 카드 집합인 벡터에 맨 위에 있는 카드를 넣어주고, 큐에서 팝을 해준다.

3. 그리고 그 다음 위에 있는 카드를 큐에 다시 푸쉬를 해준뒤 다시 팝을 해준다.

4. 위 과정을 큐가 비어있을 때까지 반복을 해주고, 위에서 만들어둔 벡터를 출력하면 정답이다.

코드

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int N;
queue<int> q;
vector<int> v;

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

    cin >> N;
    for (int i=1; i<=N; i++) {
        q.push(i);
    }
    
    while (!q.empty()) {
        v.push_back(q.front());
        q.pop();
        q.push(q.front());
        q.pop();
    }
    
    for (int i=0; i<N; i++) {
        cout << v[i] << " ";
    }
    
	return 0;
}