(C++) 백준 11509 풍선 맞추기

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

첨에 LIS 비슷하게 1씩 감소하는 LIS 로 ...풀었는데 시간초과 나왔다
반례가 1 2 3 4 5 이런식으로 오름차순이고 N이 최대면.. 10의 12승이라서 시간초과 날수밖에 없었던거같다..ㅎ

오히려 단순하게 생각해야 풀렸다
for문을 한번만 돌리면서
만약 입력받은 위치값 x에 대해 x+1 위치에 풍선이 있으면 (arr[x+1]>0)
그 위치에서 사용한 화살을 재사용할수 있으므로 arr[x+1]-=1했다

그리고 x+1이 있던 없던 상관없이 입력받은 풍선 위치 x에 대해서는
터트려야 하므로 arr[x]+=1 해야한다

#include <iostream>
using namespace std;

int N,x,MAX;
int arr[1000005];
bool isVisited[1000005];

int main(){

    cin>>N;

    for(int i=0; i<N; i++) {
        cin>>x;

        if(arr[x+1]>0) arr[x+1]--;
        arr[x]++;
        if(MAX<x) MAX=x;
    }

    int ans=0;
    for(int i=1; i<=MAX; i++) ans+=arr[i];

    cout<<ans;
}