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

1. 문제 개요

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

2164번: 카드2

1-1. 설명

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지 번호가 붙어있으며, 1번 카드가 제일 위에 있고 N번 카드가 제일 아래인 상태로 카드가 놓여있다. 이제 다음과 같은 동작을 카드가 한장 남을때 까지 반복한다. 우선 제일 위에 있는 카드를 바닥에 버리고, 그 다음 제일 위에 있는 카드를 맨 아래로 보낸다. N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성한다. 

 

 

1-2. 제한 사항

 - 첫째 줄에 정수 N이 주어지며, 1이상 500,000이하

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

---

2. 구현

2-1. 풀이

설명과 동일하게 1부터 N까지의 숫자를 queue에 저장하고 버릴때는 pop하며, 뒤로 보낼때는 front를 통해 저장한 후 pop하여 push를 진행한다. 이를 한장만 남을 때까지 반복하였다. 

2-2. 코드

#include <iostream>
#include <queue>

using namespace std;

int main(void) {
	int N;
	queue<int> cards;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cards.push(i);
	}

	while (N > 1) { // 한장남을 때까지 반복
		cards.pop(); // 처음 카드는 버림
		int card = cards.front();
		cards.pop();
		cards.push(card);
		// 두번째 카드는 뒤로 보냄
		N--;
	}
	cout << cards.front() << endl;
}