큰 방에 N개의 풍선이 떠있다. 풍선들은 왼쪽부터 오른쪽까지 일렬로 있다.

수완이는 화살 가지고 사냥 연습하는 것을 좋아한다. 수환이는 임의의 높이에서 화살을 왼쪽에서 오른쪽으로 쏜다.

화살은 선택된 높이 H에서 풍선을 마주칠 때까지 왼쪽에서 오른쪽으로 이동한다.

화살이 풍선을 마주치는 순간, 풍선은 터지고 사라진다.

화살은 계속해서 진행해 가는데 높이는 1 줄어든다.

따라서 화살이 높이 H에서 이동 중이었다면 풍선을 터트린 후에는 높이가 H-1이 된다.

수완이는 모든 풍선을 터트리되 가능한 적은 수의 화살을 사용하고자 한다.

수완이를 도와 가장 적은 수의 화살 개수를 구해보자.

풍선 터트리기(BALONI) timer 2s memory 128MB

풍선 터트리기(BALONI) 2s 128MB