문제

입력 , 출력

solution

import sys

input = sys.stdin.readline
n = int(input())
arr = list(map(int, input().split()))
res = [0 for i in range(1000001)]
cnt = 1
res[arr[0] - 1] = 1
for i in range(1, n):
    if res[arr[i]] >= 1:
        res[arr[i]] = 0
        res[arr[i] - 1] += 1
    else:
        cnt += 1
        res[arr[i] - 1] += 1
print(cnt)

설명

n의 개수가 1,00,000개라서 n제곱 복잡도로 하면 시간 초과가 날것같아서
O(n) 복잡도로 생각을 해봤다.
처음에는 앞에 풍선의 높이보다 1작을경우에 넘어가고 아닐경우에는 화살의 개수를 늘렷다.
매우 틀린답..

그래서 해당 높이에 화살이 날라가고 있는지 체크하는 배열 res를 만들었다.
해당 높이에 화살이 있으면 화살의 개수를 0 으로 만들고 높이 -1 index를 1로 만들었는데 이것도 6%에서 틀렸다..

그래서 문제를 다시 읽어보니 화살을 쏘면 풍선을 맞으면 h-1만큼의 높이로 날아가는데 다음번에 못맞으면 화살이 사라지는게 아니라
h-1높이만큼 계속 날라갔다.

반례는 3 높이에 화살을 날라가고 4 높이 풍선이 있어서
새로운 화살을 쏘면 4를 맞고 3으로 내려간다.
이때 기존에 3높이 화살이 1개 있고 3 높이 화살이 1개 더 추가가 되었다.
그래서 res[arr[i]-1] 부분에 1을 더해주는 방식으로 해주니
정답...

후기

어렵당