백준 2631 파이썬

DP 문제 알고리즘
자신보다 앞에 작은 수의 개수를 테이블에 저장하여 가장 긴 증가하는 수열의 길이를 구할 수 있다.

bisect 파이썬 라이브러리

이분탐색 라이브러리가 있는지 몰랐네?? ㅋㅋㅋㅋㅋ
배열이 정렬되어 있다는 가정 하에 사용
target의 숫자가 들어갈 수 있는 위치 중에서 가장 왼쪽 인덱스는 bisect_left
들어갈 수 있는 위치의 가장 오른쪽 인덱스는 bisect_right를 활용한다.

import bisect
lst = [1,4,4,4,5,5,6,6,6,7]
print(bisect.bisect_left(lst,4))
print(bisect.bisect_right(lst,6))
print(bisect.bisect(lst,5))
'''
1
9
6
'''

lst = [1,1,1,1,4,4,4,4,7,7,7,7]
print(bisect.bisect_left(lst,3))
print(bisect.bisect_left(lst,5))
print(bisect.bisect_left(lst,7))
'''
4
8
8
'''

가장 긴 증가하는 수열 시간을 줄이기 위해 자기보다 작은 앞의 수를 찾을 때 이분탐색 사용

import bisect
import sys
def solution():
  input = sys.stdin.readline
  n = int(input())
  # num_lst = [0]*n
  lis_lst = []
  for i in range(n):
    num = int(input())
    if i == 0:
      lis_lst.append(num)
    else:
      if num > lis_lst[-1]:
        lis_lst.append(num)
      else:
        lis_lst[bisect.bisect_left(lis_lst,num)] = num
  return n - len(lis_lst)
print(solution())

dp 테이블의 마지막 숫자보다 큰 수면 뒤에 붙여주고 작거나 같은 수라면 길이 변화가 없게 기존의 dp테이블 중에서 현재 target보다 같거나 큰 수의 위치를 찾아서 치환한다.
dp의 길이를 통해 가장 긴 증가하는 수열의 길이를 구할 수 있다. 이렇게 하면 문제점은 가장 긴 증가하는 수열의 해당하는 원소는 알 수 없다. 처음에 가장 길게 증가하여 완성되어도 뒤에서 점검하면서 치환당하면서 원소가 변한다.

가장 긴 증가하는 수열 알고리즘은 다음에 한 번 정리해야겠다.

백준 2631번 줄세우기 문제는 가장 긴 증가하는 수열의 길이를 구하여 나머지 남은 숫자들만 정렬해주면 되는 문제라서 길이만 구하면 된다.