남북으로 흐르는 개울에 동서로 징검다리가 놓여져 있다.
이 징검다리의 돌은 들쑥날쑥하여 높이가 모두 다르다. 철수는 개울의 서쪽에서 동쪽으로 높이가 점점 높은 돌을 밟으면서 개울을 지나가려고 한다.
돌의 높이가 서쪽의 돌부터 동쪽방향으로 주어졌을 때 철수가 밟을 수 있는 돌의 최대 개수는?
징검다리 돌이 이어져 있지 않아도 좋으니 무조건 높은것만 밟으면서 가면 몇 개나 밟을 수 있냐?
bisect_left
를 활용하는 알고리즘이고, 그냥 이것만 활용하면 쉽게 풀린다.import sys
from bisect import bisect_left
N = int(sys.stdin.readline())
rocks = list(map(int, sys.stdin.readline().split()))
LIS = [rocks[0]]
for i in range(1, N):
if rocks[i] > LIS[-1]:
LIS.append(rocks[i])
else:
idx = bisect_left(LIS, rocks[i])
LIS[idx] = rocks[i]
print(len(LIS))