벽 고르기
면접 대비시간 제한20초메모리 제한1024 MB
최종 벽에서 인접한 높이가 다른 쌍이 K개 이하가 되도록 일부 구간의 높이를 다시 정할 때, 다시 지어야 하는 최소 구간 수를 구한다.
문제
Blotch는 벽을 하나 지었다. 벽은 N개의 구간으로 이루어져 있고, 왼쪽에서 오른쪽으로 1번부터 N번까지 번호가 붙어 있다. 급하게 지은 탓에 모든 구간의 높이가 같지는 않다. i번째 구간의 높이는 Ai미터이다.
Blotch는 일부 구간을 다시 지어 벽을 고치려고 한다. 다시 짓는 구간의 높이는 원하는 대로 정할 수 있다.
Ai ≠ Ai+1인 i (1 ≤ i < N)의 개수가 K 이하이면 Blotch는 만족한다.
Blotch가 만족하려면 벽의 구간을 최소 몇 개 다시 지어야 하는가?
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. T개의 테스트 케이스가 이어진다. 각 테스트 케이스의 첫 줄에는 벽의 구간 수 N과 인접한 구간 사이의 높이 변화 횟수의 최댓값 K가 주어진다.
둘째 줄에는 N개의 정수가 주어진다. i번째 정수는 i번째 구간의 높이 Ai이다.
출력
각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 Blotch가 만족하기 위해 다시 지어야 하는 구간의 최소 개수이다.
제한
- 1 ≤ T ≤ 100.
- 모든 i에 대해 1 ≤ Ai ≤ 1000.
- 0 ≤ K ≤ N.
힌트
첫 번째 예시에서 벽의 구간 수는 N = 8이고, 인접한 구간 사이의 높이 변화가 K = 2 이하이면 Blotch는 만족한다. Blotch는 다음을 할 수 있다.
- 2번째 구간을 높이 300으로 다시 짓는다.
- 6번째 구간을 높이 200으로 다시 짓는다.
- 8번째 구간을 높이 800으로 다시 짓는다.
그러면 구간의 높이가 300, 300, 300, 300, 200, 200, 800, 800인 벽이 되어 Blotch는 만족한다.
두 번째 예시에서 벽의 구간 수는 N = 5이고, 인접한 구간 사이의 높이 변화가 K = 3 이하이면 Blotch는 만족한다. Blotch는 이미 만족하고 있으므로 아무 구간도 다시 지을 필요가 없다.
세 번째 예시에서 벽의 구간 수는 N = 7이고, 인접한 구간 사이의 높이 변화가 K = 3 이하이면 Blotch는 만족한다. Blotch는 다음을 할 수 있다.
- 2번째 구간을 높이 10으로 다시 짓는다.
그러면 구간의 높이가 10, 10, 40, 10, 10, 30, 30인 벽이 되어 Blotch는 만족한다.
네 번째 예시에서 벽의 구간 수는 N = 10이고, 인접한 구간 사이의 높이 변화가 K = 2 이하이면 Blotch는 만족한다. Blotch는 다음을 할 수 있다.
- 5번째 구간을 높이 60으로 다시 짓는다.
- 6번째 구간을 높이 60으로 다시 짓는다.
그러면 구간의 높이가 30, 30, 60, 60, 60, 60, 60, 60, 30, 30인 벽이 되어 Blotch는 만족한다.