[백준-2346] 풍선 터뜨리기

2346번: 풍선 터뜨리기

 

풍선을 터뜨리고 각 index 별로 터지는 순서를 적어야하는 줄 알고 삽질한 문제이다.

일단 시간제한이 2초에 입력값의 범위가 1000까지라 n^2 의 복잡도로는 널널하게 패스하기 때문에 넉넉잡아 풀어도 상관 없을거라고 생각한다.

로직은 단순하게 index 를 돌려가면서 0이 되었을 때, n-1 이 되었을 때 나누어서 풀면 된다. 코드는 다음과 같다.

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <queue>

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, input;
	deque<int> dq;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> input;
		dq.push_back(input);
	}
	
	int check[1001] = { 0, };
	int cnt = 2, cx, cidx = 0;
	check[0] = 1;
	cout << 1 << " ";
	for(int i=2 ; i<=n ; i++){
		cx = dq[cidx];
		// cidx 풍선 터뜨림

		int ct = 0;
		if (cx < 0) {
			while (ct < -1 * cx) {
				cidx = (cidx == 0) ? n - 1 : cidx - 1;
				if (check[cidx] != 0) continue;
				else ct++;
			}
		}
		else {
			while (ct < cx) {
				cidx = (cidx == n - 1) ? 0 : cidx + 1;
				if (check[cidx] != 0) continue;
				else ct++;
			}
		}
		check[cidx] = i;
		cout << cidx+1 << " ";
	}

	return 0;
}