문제

남북으로 흐르는 개울에 동서로 징검다리가 놓여져 있다.

이 징검다리의 돌은 들쑥날쑥하여 높이가 모두 다르다. 철수는 개울의 서쪽에서 동쪽으로 높이가 점점 높은 돌을 밟으면서 개울을 지나가려고 한다.

돌의 높이가 서쪽의 돌부터 동쪽방향으로 주어졌을 때 철수가 밟을 수 있는 돌의 최대 개수는?

제한 사항

• 1 ≤ N ≤ $3×10^3$ 인 정수
• 1 ≤ $A_i$ ≤ $10^8$ 인 정수

풀이

아이디어

• 문제가 너무 조건이 허술한데.. 뭘 원하는건지...... 정확히 문제에서 원하는 건 이런거다.

징검다리 돌이 이어져 있지 않아도 좋으니 무조건 높은것만 밟으면서 가면 몇 개나 밟을 수 있냐?

• 그렇다면 최장 증가 부분 수열(LIS)가 생각나야 한다.
• 이 알고리즘은 bisect_left를 활용하는 알고리즘이고, 그냥 이것만 활용하면 쉽게 풀린다.

코드

• LIS라는 배열을 하나 만든다.
• rocks 배열에서 LIS의 마지막보다 "큰"(이상 안됨. 초과여야함) 것이 들어온다면 LIS에 append를 해주고, 아니라면 bisect_left를 통해서 해당 돌의 높이가 LIS에 어디에 들어갈 수 있는지 인덱스를 얻어낸 다음 그 인덱스 자리에 그 높이를 넣는다.
• 이런 식으로 반복하다보면 반복문이 끝나게 되고, 최종 정답은 LIS 배열의 길이이다.

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))