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

문제

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

2346번: 풍선 터뜨리기

 

문제풀이

deque 말고 벡터를 이용해서 풀었다.

풍선을 터뜨려서 나온 종이의 값이 양수이면 오른쪽으로, 음수이면 왼쪽으로 이동한다.

balloon[].first는 풍선 안에 있는 종이의 값, balloon[].second는 해당 풍선이 몇 번째 인지를 나타낸다.

while문에서 풍선의 번호를 출력하고, 종이의 값을 num에 대입하고, balloon[idx]를 erase 한다.

이렇게 되면 풍선은 idx이상의  풍선들은 왼쪽으로 당겨진다.

num이 양수이면 이미 당겨졌으므로 num은 num값에 -1을 한 후 balloon.size을 나머지 연산을 한 값을 저장한다.

그다음 idx는 오른쪽으로 이동해야 하는 칸 값인 num을 더하고 idx가 balloon의 size를 넘길 수도 있으므로 다시 balloon.size로 나머지 연산 값을 저장한다.

num이 음수일 때도 같은 알고리즘으로 푼다.

 

 

코드

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int N(0), idx(0), num(0);
	cin >> N;
	vector<pair<int, int>>balloon(N, { 0,0 });

	for (idx = 0; idx < N; ++idx) {
		cin >> balloon[idx].first;
		balloon[idx].second = idx + 1;
	}
	idx = 0;


	while (balloon.size() > 1) {
		cout << balloon[idx].second << ' ';
		num = balloon[idx].first;
		balloon.erase(balloon.begin() + idx);

		if (num > 0) {
			num = (num - 1) % balloon.size();
			idx = (idx + num) % balloon.size();
		}
		else {
			num %= (int)balloon.size();
			idx += num;
			if (idx < 0) {
				idx += balloon.size();
			}
			idx %= balloon.size();
		}
	}
	cout << balloon[0].second;
}