USACO 2004 U S Open- The Cow Lineup > 문제은행 : 정보올림피아드&알고리즘




2092 : The Cow Lineup

제한시간
1000 ms   
메모리제한
256 MB   
해결횟수
3 회   
시도횟수
4 회   

문제

농부 철수는 N(1<=N<=100,000)마리의 소를 소유하고 있다. 

지금 이 N마리의 소가 한 줄로 서 있고, 각각의 소는 1부터 K(1<=K<=10,000)사이의 번호가 붙어 있는데, 

이는 소의 품종을 식별하는 용도로 사용된다. 

 

예를 들어 14마리의 소가 다음과 같이 서 있다고 하자. 숫자는 위에서 언급했듯 해당 소의 품종을 의미하는 식별 번호다.

 

1 5 3 2 5 1 3 4 4 2 5 1 2 3


농부 철수는 수학적 감각이 탁월한 농부여서 위의 품종번호들의 연속된 나열을 수열로 보고, 

해당 수열의 특성을 알아차리고자 한다. 예컨대, 3 4 1 3은 위 수열의 부분 수열(연속일 필요는 없다.)임을 알 수 있다.

농부 철수를 위 수열에서 가능한 모든 부분 수열 중 1부터 K의 수를 이용해서 

구성할 수 없는 가장 짧은 부분 수열의 길이를 찾고자 한다. 

하지만 소의 마리수가 너무 많을 경우에는 수를 헤아리는데 너무 많은 시간이 들게 되므로

이러한 문제를 푸는 프로그램을 작성하여 농부 철수를 도와주자.


입력형식

첫 번째 줄에 N과 K가 입력되고 그 다음 줄부터 N개의 줄에는 각 소의 품종을 뜻하는 번호가 순서대로 주어진다.


출력형식

첫 줄에 부분 수열을 만들 수 없게 되는 최소 길이를 출력한다.


입력 예

14 5
5
3
2
5
1
3
4
4
2
5
1
2
3

출력 예

3

Hint!

길이가 1인 부분 수열은 존재하고, 25개의 길이가 2인 부분 수열 역시 존재하나, 길이가 3인 부분 수열 중에는 2,2,4가 존재하지 않는다.




경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP