대한 어린이집에 올해 입학한 어린이들이 놀이터에 한 줄로 서있다. 모든 어린이들에게는 입학할 때 주어진 번호가 있고 모두 옷에 번호표를 달고 있다. 그런데 어린이들은 아직 번호 순서대로 줄을 잘 서지 못하므로 선생님이 다음과 같은 방법을 사용해서 번호순서대로 줄을 세우려고 한다.
방법: 줄 서있는 어린이 중 한 명을 선택하여 제일 앞이나 제일 뒤로 보낸다.
위의 방법을 사용할 때 어린이가 이동해서 빈자리가 생기는 경우에는 빈자리의 뒤에 있는 어린이들이 한 걸음씩 앞으로 걸어와서 빈자리를 메꾼다.
예를 들어, 5명의 어린이들에게 1부터 5까지의 번호가 주어져 있고, 다음과 같은 순서로 줄 서있다고 하자.
5 2 4 1 3
위 방법을 이용해서 다음과 같이 번호순서대로 줄을 세울 수 있다.
1번 어린이를 제일 앞으로 보낸다. (5 2 4 1 3 → 1 5 2 4 3)
4번 어린이를 제일 뒤로 보낸다. (1 5 2 4 3 → 1 5 2 3 4)
5번 어린이를 제일 뒤로 보낸다. (1 5 2 3 4 → 1 2 3 4 5)
위의 예에서는 세 명의 어린이를 제일 앞이나 제일 뒤로 보내 번호순서대로 줄을 세웠다. 그리고 두 명 이하의 어린이를 제일 앞이나 제일 뒤로 보내는 방법으로는 번호순서대로 줄을 세울 수 없다. 그러므로 이 경우에는 최소한 세 명의 어린이를 이동하여야 번호순서대로 줄을 세울 수 있다.
이 문제는 처음에 줄서있는 상태에서 위 방법을 이용해서 번호순서대로 줄을 세울 때 앞이나 뒤로 보내는 어린이 수의 최솟값을 찾는 것이다.
입력
입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하나씩 들어있다. 단, 어린이 수는 1이상 1,000,000이하의 정수로 제한되고, 어린이 수가 N이면 어린이들의 번호는 1부터 N까지의 정수이다.
출력
입력에서 주어진 어린이들의 줄에 대해 번호순서대로 줄을 세우기 위해 제일 앞이나 제일 뒤로 보내는 어린이 수의 최솟값을 출력해야 한다.
예제 입력 1
5 5 2 4 1 3
예제 출력 1
3
LIS는 Longest Increasing Subsequence 로써 최장증가부분수열 문제이다.
이 문제는 처음에 줄서있는 상태에서 위 방법을 이용해서 번호순서대로 줄을 세울 때 앞이나 뒤로 보내는 어린이 수의 최솟값을 찾는 것이다.
문제의 핵심은 맨 앞 또는 맨 뒤로 학생을 보낼 수 있다는 것이다.
예제
4 2 1 3 5
=> 1 4 2 3 5
=> 1 2 3 5 4
=> 1 2 3 4 5
1을 맨 앞으로 옮긴다.
4를 맨 뒤로 옮긴다.
5를 맨 뒤로 옮긴다.
결과적으로 최솟값은 3이 나온다.
증가수열에 포함하는 번호는 고정한 채 나머지 번호만 움직이면 되기 때문에, 나머지 번호의 갯수만큼 이동하면 되기 때문에 쉽게 풀 수 있다.
4 2 1 35
=> 2 3 5
가장 긴 증가수열의 길이는 3 이기에, 나머지 번호의 갯수인 즉, 최솟값은 2가 된다.
그러나 답은 3이다. 답이 맞지 않는 것을 알 수 있다.
그 이유는 어느 곳이든 보낼 수 있는 것이 아니라 맨 앞과 맨 뒤에만 보낼 수 있다.
그렇기에 가장 긴 증가수열에 포함하지 않는 나머지 번호들의 움직임이 자유롭지 않기 때문이다.
위의 예시를 다시 살펴보면, 1 4 5 가 이동했다는 것을 알 수 있다.
2와 3은 고정적이고 1 4 5가 움직였다는 의미가 된다.
42135
결론적으로가장 긴 증가수열을 찾되 연속된 수를 가진 증가수열을 찾으면 문제를 해결할 수 있다.
import sys
input=sys.stdin.readline
if __name__=="__main__":
N=int(input())
children=list(map(int,input().split()))
dp=[0]*(N+1)
long=0
for i in range(N):
idx=children[i]
dp[idx]=dp[idx-1]+1
long=max(dp[idx], long) # 연속된 가장 긴 증가수열의 길이
# 전체 수에서 가장 긴 증가수열은 그대로 나두면 나머지 수들만큼 움직이는 거임
print(N-long)
