Problemas
농부 철수는 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의 수를 이용해서
구성할 수 없는 가장 짧은 부분 수열의 길이를 찾고자 한다.
하지만 소의 마리수가 너무 많을 경우에는 수를 헤아리는데 너무 많은 시간이 들게 되므로
이러한 문제를 푸는 프로그램을 작성하여 농부 철수를 도와주자.
Entrada
첫 번째 줄에 N과 K가 입력되고 그 다음 줄부터 N개의 줄에는 각 소의 품종을 뜻하는 번호가 순서대로 주어진다.
Salida
첫 줄에 부분 수열을 만들 수 없게 되는 최소 길이를 출력한다.
Ejemplo
14 5
5
3
2
5
1
3
4
4
2
5
1
2
3
3
길이가 1인 부분 수열은 존재하고, 25개의 길이가 2인 부분 수열 역시 존재하나, 길이가 3인 부분 수열 중에는 2,2,4가 존재하지 않는다.
Fuente
USACO 2004 US Open
Debes iniciar sesión para escribir código.