https://www.acmicpc.net/problem/2232
문제를 읽어보면 각 지뢰의 충격 강도보다 큰 힘이 전달될 경우 지뢰가 터지면서 그 지뢰의 폭발력(충격 강도와 같은 값)이 양 옆의 지뢰로 전달된다고 한다.
즉, 3 4 5 4 4 로 지뢰가 주어질 경우 3번째 지뢰를 터트리면 1,2,4번째 지뢰는 터지지만 5번째 지뢰는 왼쪽의 지뢰가 가진 폭발력보다 낮은 충격 강도가 아니기 때문에 터지지 않는다.
그러므로, 지뢰가 터지는 경우는 양 옆의 지뢰중 어느 하나라도 자신의 충격 강도보다 큰 값을 가질 때다. 어디선가 터져서 연쇄 반응을 일으킬 때 필연적으로 어느 쪽에서든지 터지는 상황이 올 때 해당 지뢰도 터지기 마련이다.
반대로 생각해보면 양 쪽 모두 자신의 충격 강도와 같거나 작은 상황이면 터지지 않는다는 말이다. 수동으로 터트려야 한다!
이걸 그대로 코드에 옮기면 된다.
#include <iostream>
int main() {
int N, arr[50001]{0};
scanf("%d", &N);
for (int i = 1; i <= N; i++) {
scanf("%d", &arr[i]);
}
for (int i = 1; i <= N; i++) {
if (arr[i - 1] <= arr[i] && arr[i] >= arr[i + 1]) {
printf("%d\n", i);
}
}
}
'프로그래밍 > 알고리즘' 카테고리의 다른 글
1485 정사각형 (0) | 2022.08.31 |
---|---|
1461 도서관 (0) | 2022.08.30 |
2226 이진수 (0) | 2022.08.29 |
1262 알파벳 다이아몬드 (0) | 2022.08.20 |
9020 골드바흐의 추측 (0) | 2022.08.19 |
댓글