[BOJ/백준 18115][C++] 카드 놓기

문제

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

백준 18115

백준 18115

 

문제 내용

사용할 수 있는 기술 3가지가 있다.

1. 제일 위의 카드 1장을 바닥에 내려놓는다.
2. 위에서 두 번째 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다.
3. 제일 밑에 있는 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다.

이 기술들을 사용하여 카드를 다 내려놓았을 때, 카드의 순서가 위에서부터 순서대로 1,2,3,..., N이 되어있다.

초기 카드 상태를 구하는 문제이다.

 

문제 풀이

역순으로 계산해야 하기 때문에 조금 헷갈렸다.

초기 상태 : ?????????
기술 사용 순서: 2 3 3 2 1 (예시)
최종 상태 : 5 4 3 2 1

우리는 최종 상태와, 기술 사용 순서를 가지고 문제를 풀어야 한다.

따라서, 거꾸로 순서를 따라가 보면 된다.

 

기술 1번을 사용했다면, 맨 뒤에 원소를 넣어준다.

기술 2번을 사용했다면, 원소를 맨 뒤에서 두 번째에 넣어주면 된다.

기술 3번을 사용했다면, 원소를 맨 앞에 넣어준다.

 

카드를 앞, 뒤로 넣을 수 있어야 하기 때문에 deque를 사용하여 문제를 풀었다.

 

코드

#include <iostream>
#include <vector>
#include <deque>

using namespace std;

/*
카드의 상태가 위에서부터 1,2,3,..n으로 끝남.
기술의 순서를 입력으로 받음
=> 역순으로 계산해보자
*/


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

	//입력
	int n; cin >> n;
	vector<int>v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	deque<int>dq;

	//문제 해결
	//입력이 1일 때: 맨 뒤에 원소를 넣어준다
	//입력이 2일 때: 원소를 맨 뒤에서 두번째에 넣어준다
	//입력이 3일 때: 원소를 맨 앞에 넣어준다
	int card = 1;
	for (int i = n - 1; i >= 0; i--) {

		if (v[i] == 1) {
			dq.push_back(card);
		}else if (v[i] == 2) {
			int tmp = dq.back();
			dq.pop_back();
			dq.push_back(card);
			dq.push_back(tmp);
		}else if (v[i] == 3) {
			dq.push_front(card);
		}

		card++;
	}

	//결과 출력
	//위에서부터 출력하라고 했으므로 뒤에서부터 출력
	for (int i = n-1; i >=0; i--) cout << dq[i] << ' ';
	cout << '\n';
}