이번 문제는 그리디 알고리즘을 이용하여 해결하였다. 풍선의 위치에 대한 리스트를 순회하며 현재 풍선이 0보다 클 경우에만 화살을 1개 증가시키고, 화살의 현재 위치를 나타내는 변수 cur을 현재 풍선의 높이-1로 선언해준다. 그리고 현재 풍선이 터졌음을 나타내기 위해 0으로 갱신해준다. 현재 위치부터 뒤까지 순회하며 cur과 같은 높이를 가진 풍선을 만나면 풍선을 0으로 갱신해주고 cur을 1 씩 감소시켜준다. 이러한 과정은 풍선이 0보다 클 경우에만 동작하므로 몇 개의 화살이 필요한지 알 수 있다.

Code

n=int(input())
tmp=list(map(int, input().split()))
arrow=0
for i in range(len(tmp)):
    if tmp[i]>0:
        arrow+=1
        cur=tmp[i]-1
        tmp[i]=0
        for j in range(i+1, len(tmp)):
            if cur==tmp[j]:
                tmp[j]=0
                cur-=1
print(arrow)