아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

오리와 박수치는 춘배

면접 대비

시간 제한1초메모리 제한1024 MB

요약
서로 다른 오름차순 꽥꽥 시각과 K가 주어질 때, 각 X_i마다 [X_i, X_i+K] 안에 박수가 있도록 하는 최소 박수 횟수를 구한다.
난이도

보통10점 중 5점

유형
그리디, 정렬, 구간
정답자
아직 제출이 없습니다

문제

춘배는 오리를 보러 왔다. 오리는 춘배가 있는 동안 총 NN번 "꽥꽥" 소리를 낸다. 오리의 소리를 듣고 감동받은 춘배는 오리에게 박수를 쳐준다.

오리가 X_iX\_i초에 "꽥꽥" 소리를 낸다면 소리를 들은 춘배는 오리에게 X_iX\_i초 이상 X_i+KX\_i+K 초 이하에 한 번 이상 박수를 쳐야한다.

만약 오리가 소리를 낸 X_iX\_i초부터 X_i+KX\_i+K초 사이에 한 번도 박수를 쳐주지 않는다면 실망한 오리는 집으로 가버린다. 예를 들어 K=2,X_i=5K=2, X\_i = 5라면 55초, 66초, 77초 중 최소 한번은 박수를 쳐야 한다.

<박수를 치는 춘배의 모습>

오리가 집으로 가지 않도록 춘배가 박수를 쳐줄 때 박수를 최소 몇 번 쳐야 하는지 구해보자.

입력

첫째 줄에 오리가 "꽥꽥" 소리를 내는 횟수 NN와 정수 KK가 공백으로 구분되어 주어진다. (1≤N≤100,000(1\le N \le 100\\,000, 0≤K≤106)0 \le K \le 10^6)

둘째 줄에 오리가 "꽥꽥" 소리를 내는 시각 X_1,X_2,...,X_NX\_1, X\_2, ..., X\_N이 공백으로 구분되어 주어진다. X_iX\_i는 서로 다르며 오름차순으로 주어진다. (1≤X_i≤106)(1 \le X\_i \le 10^6)

출력

오리가 집으로 가지 않도록 춘배가 박수를 쳐줄 때 박수를 최소 몇 번 쳐야 하는지 출력한다.

예제1

  1. 예제 1

    입력
    3 3
    1 3 7
    
    예상 출력
    2