[BOJ / C++] 2164 : 카드2

링크

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

2164번: 카드2

 

풀이 과정

큐를 이용하는 매우 간단한 문제였다.

 

1번을 제일 위에 놓고, N번까지 카드를 순서대로 놓은 뒤

1. 제일 위의 카드를 버린다

2. 1번을 수행한 이후의 카드들 중, 다시 제일 위의 카드를 제일 아래에 있는 카드 밑으로 옮긴다

 

위의 두 행동을 반복하는 문제로, 단순히 큐에 1부터 N까지 넣은 뒤

1번의 경우에는 pop()으로 제일 위의 카드를 버리고

2번의 경우에는 front()와 push()로 제일 위의 카드를 참조해서 맨 아래에 넣고, pop()으로 맨 위의 카드를 지워서

한장의 카드만 남을 때까지 반복하면 끝이다. 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;

int main() {
	ios_base::sync_with_stdio(0);  cin.tie(0); cout.tie(0);

	int N;
	queue<int> q;

	cin >> N;

	for (int i = 1; i <= N; i++) {
		q.push(i);
	}

	while (q.size() > 1) {
		q.pop();
		q.push(q.front());
		q.pop();
	}

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

	return 0;
}