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

문제

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

2346번: 풍선 터뜨리기

코드

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

int main() {
	int n;
	cin >> n;
    
	deque<int> d;
	int arr[1005] = { 0 };

	for (int i = 2; i <= n; i++) d.push_back(i);
	for (int i = 1; i <= n; i++) cin >> arr[i];

	cout << "1 ";
	int cnt = arr[1];
	while (!d.empty()) {
		if (cnt > 0) {
			cnt--;
			while (cnt--) {
				d.push_back(d.front());
				d.pop_front();
			}
			cnt = arr[d.front()];
			cout << d.front() << " ";
			d.pop_front();
		}
		else {
			cnt = -1-cnt;
			while (cnt--) {
				d.push_front(d.back());
				d.pop_back();
			}
			cnt = arr[d.back()];
			cout << d.back() << " ";
			d.pop_back();
		}
	}
}

풀이방법

터뜨릴 풍선은 덱을 이용하고, 각 풍선 안에 담긴 값은 배열을 이용해 저장했다. 풍선을 터뜨리면 풍선에서 나온 값을 cnt에 저장한다. cnt값이 양수이면 front를 뒤로 반복적으로 이동하다가 풍선을 터뜨려준다. cnt값이 음수면 back을 앞으로 반복으로 이동하다가 풍선을 터뜨린다.

고민과정

저번에 풀었던 1158번 요세푸스 문제를 응용해서 풀었다. 처음에 문제를 제대로 읽지 않고서 입력받는 숫자가 터뜨렸을 때 나오는 숫자와 같은 순서라고 생각하고 풀었다가 엄청 헤맸다..