[BOJ/Silver 4] 백준 1835 카드(C++)

문제 링크

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

 

문제

1부터 N까지의 숫자가 적힌 카드가 있다. 찬유는 이 카드를 가지고 마술을 하려 한다. 마술을 하는 순서는 다음과 같다.

1. 먼저 1부터 N까지의 숫자가 적힌 카드에서 첫 번째 카드를 가장 뒤로 옮긴다. 그러고 나서 첫 번째 카드를 책상 위에 올려놓는다. 그런데 그 카드는 1이 되어야 한다.
2. 그리고 남은 카드 중에서 첫 번째 카드를 가장 뒤로 옮기고, 또 가장 앞에 있는 카드를 가장 뒤로 옮긴다.(2번 반복) 그리고 가장 앞에 있는 카드를 책상 위에 올려놓는다. 그런데 그 카드는 2가 되어야 한다.
3. 또 남은 카드 중에서 첫 번째 카드를 가장 뒤로 옮기고... (3번 반복) 그리고 가장 앞에 있는 카드를 책상위에 올려놓는데 그것은 3이 된다.
4. 또 남은 카드 중에서 첫 번째 카드를 가장 뒤로 옮기고.. (4번 반복) 그리고 가장 앞에 있는 카드를 책상 위에 올려놓는데 그것은 4이다.
5. 위 과정을 계속 반복하여 N번 카드만 남을 때 까지 반복한다.

 

위와 같은 카드를 하려면 미리 카드의 순서를 알고 있어야 한다. 카드의 개수 N이 주어져 있을 때 위의 마술을 하기 위한 카드의 초기 순서를 구하는 프로그램을 작성하시오.

 

입력

첫 번째 줄에 카드의 개수 N(1 ≤ N ≤ 1,000)이 주어진다.

 

출력

첫 번째 줄부터 N번째 줄까지 차례로 카드의 순서를 출력한다.

 

예제 입력 1

4

예제 출력 1

2 1 4 3

 

알고리즘 분류

• 자료 구조

 

풀이

0부터 N - 1까지 덱에 차례대로 push한다.

그리고 위에서 언급된 마술의 순서대로 앞에 있는 원소를 뒤로 빼는 과정을 N번 반복한 후 앞에 있는 원소를 꺼낸다.

해당 원소가 N번 카드가 위치할 인덱스가 된다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <deque>
#include <algorithm>
#define MAX 1001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N;
deque<int> DQ;
int Card[MAX];

void input() {
	cin >> N;
}

void settings() {
	for (int i = 0; i < N; i++) {
		DQ.push_back(i);
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < i; j++) {
			int Front = DQ.front();
			DQ.pop_front();
			DQ.push_back(Front);
		}
		int Front = DQ.front();
		DQ.pop_front();
		Card[Front] = i;
	}
}

void printAnswer() {
	for (int i = 0; i < N; i++) {
		cout << Card[i] << " ";
	}
	cout << "\n";
}

int main() {
	FASTIO

	input();
	settings();
	printAnswer();

	return 0;
}