[BOJ 2346 // C++] 풍선 터뜨리기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2346번 문제인 풍선 터뜨리기이다.
문제는 아래 링크를 확인하자.

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

2346번: 풍선 터뜨리기

주어지는 풍선들을 덱(deque) 자료구조에 집어넣어 이동 및 터뜨리는 과정을 시뮬레이션하는 코드를 작성해 문제를 해결하자.

 

글쓴이의 코드는 다음 차례에 터지는 풍선을 덱의 맨 앞(front)에 오게끔 구현하였다. 이 과정에서 종이에 적혀있는 수의 부호에 따라 덱을 조작해야하는 횟수가 어떻게 변하는지에 유의해 문제를 해결하자.

 

글쓴이는 pair를 이용해 풍선의 번호와 풍선 안에 들어있는 수를 함께 저장시키는 방식으로 구현해 문제를 해결하였다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <deque>
using namespace std;

int N;
deque<pair<int, int>> dq;

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

	cin >> N;
	for (int i = 1; i <= N; i++) {
		int d; cin >> d;
		dq.push_back(make_pair(d, i));
	}

	cout << dq.front().second << ' ';
	while (dq.size() > 1) {
		int mv = dq.front().first; dq.pop_front();

		if (mv > 0) {
			while (mv > 1) {
				dq.push_back(dq.front());
				dq.pop_front();
				mv--;
			}
		}
		else {
			while (mv < 0) {
				dq.push_front(dq.back());
				dq.pop_back();
				mv++;
			}
		}
		cout << dq.front().second << ' ';
	}
}