문제4090--보석 집게

4090: 보석 집게

[만든사람 : ]
시간제한 : 1.000 sec  메모리제한 : 128 MiB

문제 설명

세종이는 다양한 크기와 색을 갖는 보석들을 운반하고 있다. 보석들의 크기는 1부터 m까지의 자연수이고, 총 n개의 보석들이 작업대 위에 일렬로 놓여있다.
세종이는 여러 개의 보석들을 한 번에 집을 수 있는 커다란 집게를 가지고 있다. 이 집게는 균형값(k)이라는 것이 있는데, 집게로 집어내는 보석들의 최대 크기와 최소 크기의 차이가 균형값보다 작거나 같아야 안정적으로 보석들을 집어 올릴 수 있다.

예를 들어 작업대 위에 놓인 보석의 크기가 순서대로 2 3 2 4 5 3 4 3 4 5 6 3 6 일 때, 균형값이 2인 집게를 이용할 때는 한 번에 총 7개까지의 보석을 집을 수 있다.
(다음 그림과 같이 최댓 크기와 최소 크기의 차이가 2인 4 5 3 4 3 4 5의 보석을 집을 수 있다.)



작업대 위에 일렬로 놓인 보석들의 크기가 주어질 때 집게를 이용하여 집어낼 수 있는 보석들의 최대 개수를 구하는 프로그램을 작성하시오. 




입력 설명

첫 번재 줄에는 n, m, k가 공백으로 구분되어 입력된다.
\((1 \le n, m, k\le 100,000)\)

출력 설명

균형값 k인 집게로 집을 수 있는 보석의 최대 개수를 출력한다.

입력 예시 Copy

13 6 2
2 3 2 4 5 3 4 3 3 5 6 3 6

출력 예시 Copy

7 

게시판

작성자제목(댓글)
글이 없습니다.

출처/분류