백준 2164 : 카드2

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

그.. 사실 개강하고 수업 들은 것 정리해야 하는데.. 하기 싫어서.. 알고리즘을 푸려고(?????) 잠시 들렀습니다.. 시작하겠습니다.. 빨리 끝나고 12시 전에 자야지..

문제 읽기

N장의 카드가 순서대로 위에서부터 있고. 한 장 남을 때까지 반복한다. 맨 위에 있는 것 버리고 제일 위에 있는 카드를 제일 아래 있는 카드 밑으로 옮기고. 이렇게 반복했을 때 가장 마지막에 남게 되는 카드를 구해라.

결국 맨 앞과 맨 뒤만 건드리니까 자료구조 중에 queue를 택해야겠다. while문을 이용하여 카드 수를 조건문으로 확인하면 두가지 명령 box로 쉽게 해결할 수 있을 것 같다.

코드

#include<iostream>
#include<queue>
using namespace std;

int main() {
	int N;
	queue<int> que;
	cin >> N;

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

	while (N != 1) {
		que.pop();
		N--;
		temp = que.front();
		que.pop();
		que.push(temp);
	}
	cout << que.front();
	return 0; 
}

분석

엥 선생님. 제가 그렇게 멍청하지는 않습니다. 우선 queue에 어떻게 저장되는지 다 까먹었다.

보세요 선생님 큐는 이렇게 저장됩니다. 순서대로 왼쪽부터 차근차근 오른쪽에 쌓이고

que.pop(); 시에는 다음과 같이 왼쪽으로 다 정렬되어 앞으로 옵니다.

그렇다면 당연히 front();는 여기서 2를 갖겠지요. (사진 속에서는 temp 변수에 저장)

다시 맨 앞의 카드를 맨 뒤의 카드 뒤에다가 놓게 되면

다음과 같이 정렬됩니다. 와 재미있는 큐의 세상~

잊어버리지 말자. 자료구조..