![[7570] 줄세우기 (연속 최장 증가 수열, LIS)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FyBeyO%2Fbtsjwscfg8m%2FDvlRXeA3MOC3AnRms0PXP1%2Fimg.png)
728x90
7570번: 줄 세우기
입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하
www.acmicpc.net
분석
유사문제 : 2631
[2631] 줄 세우기 (2중 for문)
2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과
karla.tistory.com
추가 조건 : 이동하는 어린이를 제일 앞이나 제일 뒤로만 보낼 수 있음
➔ 바로 옆에 있는 최장 증가 수열을 구해야함
4 2 3 1 5
1. 한 명의 어린이를 뽑아서 원하는 곳에 배치
→ N(5)- 최장 증가 수열(2,3,5) 길이 = 2
2. 한 명의 어린이를 뽑아서 맨 앞이나 맨 뒤에 배치
→ N(5)- 연속 최장 증가 수열(2,3) 길이 = 3
풀이
import sys
input=sys.stdin.readline
n=int(input())
a=list(map(int, input().split()))
dp=[0]*(n+1)
res = 0
for i in range(n):
x=a[i]
dp[x]=dp[x-1]+1
res = max(res, dp[x])
print(n - res)
728x90