[백준/BOJ] 백준 2232번 : 지뢰

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

2232번: 지뢰

 

충격 강도를 초과하는 힘이 가해져야 지뢰가 터지게 되므로, 터트리려는 지뢰의 충격 강도 이하의 충격 강도를 가진 지뢰는 터트리려는 지뢰가 터지는 거에 관여할 수 없게 되므로, 충격 강도가 큰 것부터 직접 터트려가면서 문제를 해결했다.

 

코드

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

int n;
vector<int> p;
vector<pair<int, int>> power_index; //(충격 강도, 지뢰의 인덱스)

vector<int> effect(50005, 0); //지뢰가 터진 위치 체크

vector<int> result;

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

	cin >> n;

	for (int i = 0; i < n; i++) {
		int input;
		cin >> input;

		p.push_back(input);
		power_index.push_back(make_pair(input, i));
	}

	sort(power_index.begin(), power_index.end()); //충격 강도 순으로 정렬

	//충격 강도가 큰것 부터 터트려서 확인한다
	for (int i = power_index.size() - 1; i >= 0; i--) {

		int power = power_index[i].first;
		int index = power_index[i].second;

		if (effect[index] == 1) {//이미 터진 위치일때
			continue;
		}

		//index번째 지뢰를 터트린다
		result.push_back(index + 1);
		effect[index] = 1;

		int check_index;

		//터진 왼쪽 부분 확인
		check_index = index - 1;

		while (check_index >= 0) {

			if (effect[check_index] == 1) {
				break;
			}

			if (p[check_index] < p[check_index + 1]) {
				effect[check_index] = 1;
				check_index--;
			}

			else {
				break;
			}
		}

		//터진 오른쪽 부분 확인
		check_index = index + 1;

		while (check_index < n) {

			if (effect[check_index] == 1) {
				break;
			}

			if (p[check_index] < p[check_index - 1]) {
				effect[check_index] = 1;
				check_index++;
			}

			else {
				break;
			}
		}
	}

	sort(result.begin(), result.end());
	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << "\n";
	}

	return 0;
}