[12738] 가장 긴 증가하는 부분 수열 3

2023-04-25 | Algorithms / 백준 문제 풀이 모음 # Python, Gold 2

백준 문제 풀이

문제 링크

12738번: 가장 긴 증가하는 부분 수열 3

• 해설

    다른 가장 긴 증가하는 부분 수열과 비슷한 문제이다. N (1 ≤ N ≤ 1,000,000)에 3초이기 때문에 이분탐색을 사용하거나,
    이중 포문을 사용하거나 둘중 아무거나 사용해도 시간에는 문제가 없을 것이다.
      
    이번에는 이분탐색을 이용했다.
      
    LIS 와 같이 길이에 따라 최대값을 lis 배열에 넣어두고, 해당 값 보다 큰 경우 +1 을 시킨다.
    아닌 경우에는 이분탐색을 통해서 들어갈 수 있는 길이에 업데이트 시킨다.
      
  

• 답안

    import sys
      
    def bs(left, right, i):
        while(left <= right):
            mid = (left+right)//2
            if lis[mid] < nums[i]:
                left = mid + 1
            else:
                right = mid-1
        return left
      
    if __name__ == "__main__":
        N = int(sys.stdin.readline())
        nums = list(map(int, sys.stdin.readline().split()))
        cnt = 1
        lis = list( 0 for _ in range(N))
        lis[0] = nums[0]
      
        for i in range(N):
            if lis[cnt-1] < nums[i]:
                lis[cnt] = nums[i]
                cnt += 1
            else:
                left = 0
                right = cnt
                ind = bs(left, right, i)
                lis[ind] = nums[i]
      
        print(cnt)