[백준/C++] 2346번 풍선 터뜨리기

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

2346번: 풍선 터뜨리기

문제 분석

분류

자료 구조(data_structures), 덱(deque)

​

문제 설명

1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있다. 각 풍선 안에는 종이가 하나 들어있고, 종이에는 -N보다 크거나 같고, N보다 작거나 같은 정수가 하나 적혀있다. 이 풍선들을 다음과 같은 규칙으로 터뜨린다.

우선, 제일 처음에는 1번 풍선을 터뜨린다. 다음에는 풍선 안에 있는 종이를 꺼내어 그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다. 양수가 적혀 있을 경우에는 오른쪽으로, 음수가 적혀 있을 때는 왼쪽으로 이동한다. 이동할 때에는 이미 터진 풍선은 빼고 이동한다.

예를 들어 다섯 개의 풍선 안에 차례로 3, 2, 1, -3, -1이 적혀 있었다고 하자. 이 경우 3이 적혀 있는 1번 풍선, -3이 적혀 있는 4번 풍선, -1이 적혀 있는 5번 풍선, 1이 적혀 있는 3번 풍선, 2가 적혀 있는 2번 풍선의 순서대로 터지게 된다.

​

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000)이 주어진다. 다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 종이에 0은 적혀있지 않다.

​

출력

첫째 줄에 터진 풍선의 번호를 차례로 나열한다.

코드

#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

int n,top,number;
deque<pair<int, int>> dq;

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

	cin >> n;

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

	number = dq.front().second;
	cout << dq.front().first << " ";

	dq.pop_front(); // 터진거 제거

	while (!dq.empty()) {
		if (number > 0) { // 양
			for (int i = 0; i < number - 1; i++) { // 터진거 빼고 다시 deque생성
				dq.push_back(dq.front());
				dq.pop_front();
			}
			number = dq.front().second;
			cout << dq.front().first << " ";
			dq.pop_front();
		}
		else { // 음
			for (int i = 0; i > number + 1; i--) { // 반대로 deque생성
				dq.push_front(dq.back());
				dq.pop_back(); // -1 2 1 -> 1 -1 2 1 -> 1 -1 2 -> 2 1 -1 2 -> 2 1 -1
			}
			number = dq.back().second;
			cout << dq.back().first << " ";
			dq.pop_back();
		}

	}
	return 0;
}

문제풀이

문제를 보면, 값이 양수일 경우 오른쪽으로 이동하고 값이 음수일 경우 왼쪽으로 이동한다. 즉, 원형 큐 느낌이 나는 것이다. 그러므로, 앞 뒤로 push pop이 가능한 deque를 사용한다.

0 . 풍선 인덱스와 풍선이 가지고 있는 값을 한번에 관리하기 위해 pair로 선언

1 . 첫번째 풍선에 대한 작업(값 가져오고 pop하기)

2 . deque가 빌 때 까지(=모든 풍선을 터트리기) 작업을 반복한다.

​

3 . 만약 풍선의 값이 양수라면, front에 있는 풍선을 back으로 보낸다. 예를 들어, 풍선의 값이 3이면 오른쪽으로 인덱스를 3만큼 움직이는데 맨 앞에 있는 풍선 2개를 뒤로 옮기면 front에 있는 풍선은 내가 3만큼 이동하고자 했던 풍선이 된다.

4 . 그럼 그 front에 있는 풍선에 대해 작업을 진행하면 된다.

​

5 . 만약 풍선의 값이 음수라면, 반대로 한다. 음수인 경우는 왼쪽으로 이동해야하므로, back에 있는 풍선들을 front로 보낸다. 그렇게 되면 back에 있는 풍선은 내가 이동하고자 했던 풍선이 된다.

예를 들어, 값이 -3이라면 back에 있는 풍선 2개(-3+1에 절댓값)를 front로 옮기는 것이다.

​

"단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있다."

이 문장을 곰곰히 생각해보면 알 수 있을 것이다.

(풍선이 3 2 1 -3 -1일 때, 맨 첫번째 풍선 기준으로 왼쪽에는 -1 -3 1 2가 있고 오른쪽에는 2 1 -3 -1이 있다)