[Python] 백준 12015 가장 긴 증가하는 부분 수열 2

 

 

 

문제

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

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

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

 

 

 

 

 

 

 

 

난이도

골드2

 

 

 

 

내 코드

import sys

def binarySearch(value) :
    left = 0
    right = len(lis) - 1

    while left <= right :
        mid = (left + right) // 2

        if lis[mid] == value :
            return mid
        elif lis[mid] > value :
            right = mid - 1
        else :
            left = mid + 1

    return left

n = int(sys.stdin.readline())
a = list(map(int,sys.stdin.readline().split()))
lis = [0]

for value in a :
    if value > lis[-1] :
        lis.append(value)
    else :
        idx = binarySearch(value)
        lis[idx] = value

print(len(lis)-1)

 

 

 

 

 

 

 

풀이과정

LIS 알고리즘을 배웠다. 최장 증가 부분 수열의 길이를 구할 때 유용한 방법이다.

1. lis 배열을 초기화한다.

2. 입력 받은 수열 값들을 돌아가며 lis의 마지막 숫자보다 크면 lis 리스트에 추가하고 아니면 현재 수보다 바로 큰 수 자리에 대체한다.

3. lis 배열의 크기를 출력한다.