https://www.acmicpc.net/problem/2631
2631번: 줄세우기
KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기
www.acmicpc.net
이 문제는 보아도 모르겠어서
해당 블로그를 통해 이해를 하게되었다 https://ddiyeon.tistory.com/61
[백준 2631번] 줄세우기 (python)
문제 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호
ddiyeon.tistory.com
내가 제출한 코드는 다음과 같다
from bisect import bisect_left
n = int(input())
arr = []
for _ in range(n):
arr.append(int(input()))
dp = []
for i in range(len(arr)):
if not dp:
dp.append(arr[i])
else:
if dp[-1] < arr[i]:
dp.append(arr[i])
else:
dp[bisect_left(dp, arr[i])] = arr[i]
print(n - len(dp))