BOJ 2232 - 지뢰

문제

BOJ 2232 - 지뢰

일렬로 놓인 N개의 지뢰를 밟으면 인접 지뢰도 연쇄 폭발한다. 직접 밟아야 하는 지뢰 번호를 구하라 (연쇄 폭발로 터지지 않는 것들).

입력

지뢰 수 N과 각 지뢰의 위력이 주어진다.

출력

직접 밟아야 하는 지뢰의 번호를 오름차순으로 출력한다.

예제

풀이

극대점(양쪽 이웃보다 크거나 같은 위치)을 찾아 출력한다.

1. 각 지뢰의 위력을 양쪽 이웃과 비교한다
2. P[i-1] <= P[i]이고 P[i] >= P[i+1]이면 극대점이다
3. 경계(첫째, 마지막)는 한쪽만 비교한다

핵심 아이디어: 연쇄 폭발은 위력이 낮은 쪽으로 퍼지므로, 극대점은 다른 지뢰의 연쇄에 포함되지 않아 직접 밟아야 한다.

코드

#include <iostream>
#include <string>
 
using namespace std;
 
int N;
int P[50005];
 
int main()
{
  cin.tie(0)->ios::sync_with_stdio(0);
 
  cin >> N;
  for (int i = 1; i <= N; i++)
  {
    cin >> P[i];
  }
 
  for (int i = 1; i <= N; i++)
  {
    if (P[i - 1] <= P[i] && P[i] >= P[i + 1])
      cout << i << '\n';
  }
 
  return 0;
}

복잡도

• 시간: O(N)
• 공간: O(N)