JOI 2017 예선 4- 인형정리 > 문제은행 : 정보올림피아드&알고리즘




3031 : 인형정리

제한시간
2000 ms   
메모리제한
256 MB   
해결횟수
11 회   
시도횟수
106 회   

문제

희서는 장난감 마트에서 알바를 하고 있다.

오늘은 인형 코너를 정리하게 되었다.

인형 코너의 선반에는 N개의 인형을 왼쪽에서 오른쪽으로 일렬로 늘어놓을 수 있다

선반은 N개의 구획으로 구분되어 있으며, 하나의 구획에 1 개의 인형을 놓는다

이 장난감 마트는 총 M종류의 인형을 팔고 있으며, 각각 1부터 M까지 번호가 매겨져있다

선반에 정렬된 N개의 인형은 각각 M종류 중 하나이다. 또한 각 종류의 인형은 적어도 1개는 존재한다.

 

희서는 모양을 좋게 하기 위하여 같은 종류의 인형이 모두 연속으로 되도록 다음과 같은 방법으로 인형을 정렬하고자 한다.

 

* N개의 인형 중 일부를 선택하여 선반에서 꺼낸다.

* 꺼낸 인형을 좋아하는 순서대로 선반 빈 구획에 다시 집어넣는다.

 

 

입력 예 1을 보자.

먼저 놓여있는 인형의 종류는 2종류이고 왼쪽에서 오른쪽으로 1, 2, 2, 2, 1, 2, 17개의 인형이 진열되어 있다

같은 종류끼리 정렬하는데 꺼낸 인형의 개수를 최소화하려면 

왼쪽에서 1 번째와 6 번째 인형을 꺼내 왼쪽에서 1 번째로 유형 2의 인형을 왼쪽에서 6 번째로 유형 1의 인형을 배치한다

이 때 꺼낸 인형의 개수는 2 개이다. 


입력형식

입력은 1 + N 행된다. 첫 번째 줄에는 두 개의 정수 N, M (1 ≦ N ≦ 100000 1 ≦ M ≦ 20)가 공백을 구분으로 작성되었으며, 인형이 N 개의 있고, 종류가 M 종류 있다는 것을 나타낸다. 다음 N개의 행에는 각각 1 이상 M 이하의 정수가 적혀있다. N 행 중 i 번째 줄 (1 ≦ i ≦ N)에 쓰인 정수는 선반의 왼쪽에서 i 번째 구획에 놓인 인형의 종류를 나타낸다. 각 유형에 대해 적어도 1 개의 인형이 존재하는 것이 보장된다.

출력형식

정렬을 위하여 꺼낸 인형 개수의 최소값을 하나의 행에 출력한다.

입력 예

7 2
1
2
2
2
1
2
1

출력 예

2

입력 예

12 4
1
3
2
4
2
1
2
3
1
1
3
4

출력 예

7


bitwise DP

경기도 안양시 동안구 평촌대로 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