Informatica Online Judge

  Handbook [1408 / 0580]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 5   Total Tried : 7


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[koistudy.net (32nd 유재민)]

Background

재현이는 창업을 했다. 재현이가 만든 프로그램은 많은 사람들에게 사랑을 받았고 재현이에게는 주문 요청이 쇄도하기 시작했다.

재현이는 혼자 일하기 때문에 주문을 받는 일부터 프로그램을 업데이트하는 일까지 혼자서 다 해야 한다.

그중에서 재현이가 가장 하기 힘들어하는 일은 사용설명서를 작성하는 일이다. 왜냐하면, 다양한 언어를 사용하는 사람들이 재현이에게 주문하기 때문이다.

한국어, 영어, 중국어, 일본어, 프랑스어, 독일어, 야민정음, 아희, C++, Haskell 등 정말 다양한 언어를 사용하는 사람들이 주문하는 까닭에 재현이는 다양한 언어로 사용 설명서를 작성해야 한다.

재현이에게는 계속 프로그램을 업데이트 해 달라는 주문이 들어온다. 재현이는 주문이 들어올 때마다 프로그램을 업데이트 해서 배포하거나 주문이 더 올 때까지 기다린다.

프로그램을 업데이트하면 새로운 기능이 추가되거나 원래 있던 기능이 사라지기도 하므로 사용 설명서를 다시 작성해야 한다.

이 때문에 재현이는 업데이트를 자주 하려고 하지 않는다. 하지만 주문을 받고도 계속 기다리는 것도 안 좋은 것 같아 주문이 L개 들어오면 무조건 업데이트를 하려고 한다.

재현이가 가지고 있는 주문 목록에는 주문한 사람이 사용하는 언어가 적혀있다.
i번 주문부터 기다려서 j번 주문을 받을 때 프로그램을 업데이트하면 i번 사람부터 j번 사람까지 사용하는 언어 중에서 서로 다른 언어의 개수만큼 사용 설명서를 작성해야 한다.

재현이는 사용설명서를 가장 적게 작성할 수 있도록 프로그램을 업데이트하려고 한다.

사용설명서를 가장 적게 작성할 방법을 찾고 작성해야 하는 설명서의 총합을 구해 재현이를 도와주자.

Input

첫 번째 줄에 N,L,M이 주어진다.
N은 주문의 개수이고 사람들이 사용하는 언어는 1부터 M까지의 정수로 표현된다.

두 번째 줄에 N개의 수들이 주어진다.
i번 수는 i번 주문을 한 사람이 사용하는 언어를 나타낸다.

Output

작성해야 하는 사용설명서 개수의 최솟값을 출력하라.

[SubTask Info]
#1 (25%) : N ≤ 10 , L ≤ 10 , M ≤ 10
#2 (25%) : N ≤ 1,000 , L ≤ 1,000 , M ≤ 1,000
#3 (25%) : N ≤ 100,000 , L = N , M ≤ 100,000
#4 (25%) : N ≤ 100,000 , L ≤ 100,000 , M ≤ 100,000

IO Example

입력
8 4 3
3 2 2 1 2 1 2 1

출력
5

(설명) 1~3 구간에서 2개, 4~7 구간에서 2개 (구간의 길이가 최대 4이다), 8~8 구간에서 1개를 작성하여 총 5개를 작성하는 것이 최소이다.

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