[백준알고리즘] 2631번: 줄세우기 -Python

[백준알고리즘] 2631번: 줄 세우기 -Python

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

2631번: 줄세우기

LIS문제이다.

 

세워져있는 상태에서 정상적으로 줄 서있는 학생들의 수를 구해서 전체 학생 수에서 빼주면 움직이는 최소 횟수가 된다.

 

범위가 작기 때문에 간단한 DP형태의? 이중 for문을 도는 형태로 구현해도 통과할 것 같았지만 이분 탐색을 이용해서 LIS 길이를 구하는 방법을 사용했다.

 

아래 코드는 bisect.bisect_left()를 사용해서 구해준 방법과 직접 이분 탐색 코드를 짠 거다.

from bisect import bisect_left

n = int(input())
childeren = [int(input()) for _ in range(n)]

def find(idx):
    return bisect_left(lis, childeren[idx])

# LIS
lis = []
for i in range(n):
    if not lis or lis[-1] < childeren[i]:
        lis.append(childeren[i])
    elif lis[-1] > childeren[i]:
        lis[find(i)] = childeren[i]

print(n-len(lis))

n = int(input())
childeren = [int(input()) for _ in range(n)]

def find(idx):
    s, e = 0, len(lis)-1
    while s < e:
        m = (s+e)//2
        if lis[m] < childeren[idx]:
            s = m+1
        else:
            e = m
    return e

# LIS
lis = []
for i in range(n):
    if not lis or lis[-1] < childeren[i]:
        lis.append(childeren[i])
    elif lis[-1] > childeren[i]:
        lis[find(i)] = childeren[i]

print(n-len(lis))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다