Informatica Online Judge

  인형 정리 [1833 / 0729]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 12   Total Tried : 16


The Champion of this Problem (C++) : t1234 - 10ms / 607byte
My Best Submission (C++) : N/A

[JOI 16/17 예선]

Background

경곽이는 장난감 가게를 운영하고 있다.

오늘은 가게 내에 봉제인형 코너를 정리하고자 한다.

인형코너의 진열장에는 $n$개의 인형이 왼쪽으로부터 오른쪽으로 한 줄로 나열되어 있다.

진열장의 구성은 $n$개의 구역으로 나눠지며, 1개의 구역에는 1개의 인형이 놓여있다.

이 장난감 가게는 모두 $m$ 종류의 인형을 팔고 있다.

각각 $1$부터 $m$까지의 번호가 부여되어 있다.

진열장에 나열된 $n$개의 인형은 각각 $m$종류 중 하나이다.

또 각각의 종류의 인형은 적어도 1개 이상은 존재한다.

잘 정리하기 위해서 같은 종류의 인형은 모두 연속된 진열장에 놓이도록 인형을 정리하고자 한다.

인형을 정리하기 위해서 다음과 같은 방법으로 인형의 배치를 바꾸기로 했다.

- $n$개의 인형들 중 몇 개를 골라 진열장으로부터 뺀다. 나머지 인형들의 위치는 변함이 없다.
- 빼낸 인형들을 원하는 위치의 진열장 빈 자리에 채운다.

위치를 바꾼 후 같은 종류의 인형이 모두 연속되도록 배치해야한다.

배치를 바꾸기 위해 바꾼 인형의 수를 최솟값을 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에는 2개의 정수 $n$, $m$이 공백으로 구분되어 입력된다.

인형은 $n$개가 있고, 종류는 $m$가지 종류가 있다.

다음 줄부터 $n$줄에는 각각 1이상 $m$이하의 정수가 입력된다.


[입력값의 정의역]

$1 ≦ N ≦ 100000$
$1 ≦ M ≦ 20$

Output

원하는 배치를 하는데 교한해야할 인형 개수의 최솟값을 출력한다.

IO Example

입력
7 2
1
2
2
2
1
2
1

출력
2

입력2
12 4
1
3
2
4
2
1
2
3
1
1
3
4

출력2
7

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]