[BOJ] 3307번: Balloons

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

정말 긴 시간동안 고통받았습니다 ㅠ_ㅠ 핵심 아이디어는, i번째 풍선의 반지름이 a[i]라고 할 때, i > j에 대해 a[i] < a[j]이면 i번째 풍선은 j번째 이후의 풍선의 크기에 아무런 영향을 주지 않습니다.(i번째 풍선에 닿기 전에 반드시 j번째 풍선에 닿기 때문입니다.)

이 사실을 이용해 스택을 두어 새로운 풍선의 크기를 정해주고, 그 풍선보다 반지름이 작은 모든 풍선을 스택에서 제거하는 방식으로 O(N)에 해결할 수 있습니다.

https://github.com/blisstoner/BOJ/blob/master/3307.cpp