데크 소트
시간 제한2초메모리 제한128 MB
입력 순서대로 주어지는 N개의 정수를 덱의 앞이나 뒤에 넣거나 새 덱을 만들어 배치해서, 이어 붙였을 때 비내림차순이 되도록 하는 최소 덱 개수를 구합니다.
문제
데크는 앞과 뒤 양쪽에서 원소를 넣거나 뺄 수 있는 자료구조이다.
정수 N개가 순서대로 주어진다. 각 정수는 입력된 순서를 지켜 다음 세 가지 방법 중 하나로 데크들에 넣어야 한다.
- 이미 있는 데크 하나의 맨 앞에 넣는다.
- 이미 있는 데크 하나의 맨 뒤에 넣는다.
- 새 데크를 만들고 그 데크에 넣는다.
모든 정수를 넣은 뒤, 만들어진 데크들을 어떤 순서로 이어 붙였을 때 전체 수열이 오름차순(비내림차순)이 되도록 하려고 한다. 필요한 데크 수의 최솟값을 구하시오.
입력
첫째 줄에 수의 개수 N이 주어진다. N은 1,000 이하의 자연수이다.
다음 N개의 줄에는 정수가 한 줄에 하나씩 주어진다. 각 정수는 -1,000 이상 1,000 이하이며, 같은 수가 여러 번 나올 수 있다.
출력
데크들을 이어 붙여 오름차순으로 만들기 위해 필요한 데크 수의 최솟값을 첫째 줄에 출력한다.