대표 점 timer 1s memory 512MB

직선 위에 N개의 서로 다른 점이 있다. 각 점은 1 이상 M 이하의 고유 색깔이 있으며 M ≤ N을 만족한다. 우리는 N개의 점들 중 1개 이상의 점을 선택하여 ‘대표 점’으로 선정할 것이다. ‘대표 점’을 선정할 때에는 반드시 아래 조건을 만족해야 한다.

● ‘대표 점’이 아닌 임의의 점 p에 대하여 p와 가장 가까운 ‘대표 점’은 p와 색깔이 같아야 한다. 만약 가장 가까운 점이 여러 개일 경우 그 중 적어도 하나와만 같으면 된다. 

아래 그림과 같이 6개의 점이 1번에서 6까지 번호가 매겨져 있다고 해보자. 2, 4, 6번 점을 ‘대표 점’으로 선택하면 조건을 만족하지만 2, 4번 점만을 ‘대표 점’으로 선택하면 6번 점과 가장 가까운 ‘대표 점’이 6번 점과 다른 색이므로 조건을 만족하지 않는다.

‘대표 점’을 너무 많이 선택하면 대표라는 의미에 맞지 않으므로, 최소 개수의 점들만 뽑아서 ‘대표 점’으로 선정하고 싶다. N개의 점들이 주어지면 대표 점을 선정하는 프로그램을 작성하여라.