[BOJ] 12015 : 가장 긴 증가하는 부분 수열 2 (Python3)

문제: https://www.acmicpc.net/problem/12015

풀이

가장 긴 증가하는 부분 수열이 뭔지, 그리고 그것을 어떻게 이진탐색으로 풀어야할지 이해가 되지 않아 풀기 힘들었던 문제이다.

결국 다른 풀이를 참고해 아래와 같이 소스코드를 작성했다.

1. 해당 수열을 넣어둘 ans 배열에 미리 최솟값 0을 넣어둔다. (arr의 원소보다 작은 수)
2. 반복문으로 arr[i]가 ans의 가장 마지막 값보다 크다면 ans에 그 값을 넣어준다.
3. 만약 작다면, bisect_left로 나오는 자리를 arr[i]로 바꿔준다.
4. 반복문이 다 끝나면 ans의 길이에서 -1 한 값을 return한다. (처음에 0을 추가했으므로)

소스코드

import sys, bisect
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().strip().split()))
ans = [0]

def solution():
    for i in range(n):
        if arr[i] > ans[-1]:
            ans.append(arr[i])
        elif arr[i] < ans[-1]:
            num = bisect.bisect_left(ans, arr[i])
            ans[num] = arr[i]
    return len(ans)-1

print(solution())

참고

https://jason9319.tistory.com/113 https://shoark7.github.io/programming/algorithm/3-LIS-algorithms#5