[백준(BOJ) 2164번] 카드2 (C++)

문제 링크

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

 

문제 정보

입력

첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.

출력

첫째 줄에 남게 되는 카드의 번호를 출력한다.

 

풀이

 문제의 조건을 잘 읽어서 큐로 풀어야 한다는 것을 파악하면 쉽게 해결할 수 있다. 문제에서 1부터 n까지의 카드를 1이 제일 위로 오게 순서대로 밑으로 놓여져 있고, 제일 위에 있는 카드를 버린다는 것을 통해 먼저 들어간 것이 먼저 나오는 (FIFO) 구조를 떠올릴 수 있다. 

 

소스 코드

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n;
	cin >> n;
	
	queue<int> Q;
	
	for (int i = 1; i <= n; i++) {
		Q.push(i);
	}
	
	while (Q.size() != 1) {
		Q.pop();
		int temp = Q.front();
		Q.push(temp);
		Q.pop();
	}
	
	cout << Q.front();
	
	return 0;
}