[백준 단계별 풀이] #12015 가장 긴 증가하는 부분 수열

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)

출력

 

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

처음에 짠 코드 

N = int(input())
arr = list(map(int, input().split()))
ref = [1 for _ in range(N)]

for i in range(N):
    for j in range(i):
        if arr[i] > arr[j]:
            ref[i] = max(ref[i], ref[j]+1)

print(max(ref))

처음에는 LIS 문제인 줄 알고 풀었다. 

근데 시간 초과로 틀림

수열의 크기가 백만 까지 가능하기때문에, 더 효율적인 탐색이 필요함

그래서 이분 탐색 문제가 된다. 

 

ref에다가 작은 값 부터 입력을 해서 길이를 유지해가는 식이다. 

방법은 https://suri78.tistory.com/199 에 엄청 잘 나와있음. 

 

코드 

import sys

def find(target, ref):
    l, h = 1, len(ref) - 1
    while l < h :
        mid = (l + h) //2
        if ref[mid] > target:
            h = mid
        elif ref[mid] < target:
            l = mid+1
        else:
            l = h = m
    return h

N = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
ref = [0]

for a in arr:
    if ref[-1] < a:
        ref.append(a)
    else:
        ref[find(a, ref)] = a

print(len(ref)-1)

해답을 보고 풀었는데도 계속 틀렸다. 

이분탐색 코드 마지막에 l = h = m 을 계속 l = m 만 해주어서 틀림.