백준 온라인 저지, 이진탐색 / 3745번: 오름세 (파이썬 / 백준 골드문제)

문제

https://www.acmicpc.net/problem/3745

문제 정의

주식투자를 좋아하는 정인이는 주가의 오름세를 살펴보려고 한다.
정인이는 n일 동안 매일 주가를 적어놓았고, 여기서 오름세를 찾아보려고 한다.
n일 동안의 주가를 p1, p2, ..., pn이라고 했을 때, 오름세란 부분수열 pi1 < pi2 < ... < pik (i1 < i2 < ... ik)을 말한다.
n일 동안 주가가 주어졌을 때, 가장 긴 오름세를 찾는 프로그램을 작성하시오.

입력

입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다. 주가는 한 개 이상의 공백으로 구분되어 있으며, 그 외의 위치에서도 자유롭게 나올 수 있다. 주가는 100,000보다 작거나 같은 자연수이다.

출력

각 테스트 케이스에 대해서 입력으로 주어진 주가의 가장 긴 오름세의 길이를 출력한다.

예제 입력 1

6
5 2 1 4 5 3
3
1 1 1
4
4 3 2 1

예제 출력 1

3
1
1

접근 방법

- 가장 긴 부분 수열을 nlogn으로 구현해 가장 긴 오름세를 찾는다.

코드

# https://www.acmicpc.net/problem/3745
# 접근 방법
# 가장 긴 부분 수열을 nlogn으로 구현해 가장 긴 오름세를 찾는다.
import sys
input = sys.stdin.readline
while True:
    n = input()
    if not n:
        break
    n = int(n)
    array = list(map(int, input().split()))
    dp = [0 for _ in range(n)]
    dp[0] = array[0]
    length = 1
    for x in array[1:]:
        start = 0
        end = length - 1
        index = 0
        while start <= end:
            mid = (start + end) // 2
            
            if dp[mid] < x:
                start = mid + 1
                index = max(index, mid+1)
            
            else:
                end = mid - 1
                
        length = max(index+1, length)
        dp[index] = x

    print(length)