[python] 백준 2352 반도체 설계

 

 

문제 해결

• 가장 길게 오름차순 수열을 만들수 있는 LIS (Longest Increasing Subsequence) 문제
• 원소 하나씩 살펴보면서 가장 최근 이은 값도가 크면 하나 더해주고 작은 값이 나오면 이분탐색 통해 이전 값들에서 하나에 예약 연결한다 생각하고 value값을 바꿔놔도 문제 없다

CODE

import sys
input = sys.stdin.readline
from bisect import bisect_left

if __name__ == "__main__":
    n = int(input())
    A = list(map(int, input().split()))
    link = []
    for d in A:
        if not link or link[-1] < d:
            link.append(d)
        else:
            link[bisect_left(link,d)] = d
    print(len(link))