[구름LEVEL] 근묵자흑

level.goorm.io/exam/47881/%EA%B7%BC%EB%AC%B5%EC%9E%90%ED%9D%91/quiz/1

구름LEVEL

---

-풀이-

 

모든 수를 같게만드려면, 그 수열중 최솟값으로 다 바꿔야 한다. 

최솟값을 포함한 k개만큼을 최솟값으로 변경 시킨뒤, k개의 양끝을 기준으로 k-1개를 늘리고, 다시 그 양끝을 기준으로 k-1개를 늘리면된다.

따라서

처음 1번은 최솟값을 기준으로 k개를 변경시키는 작업, 나머지 횟수는 n-k개를 k-2개로 나누는 작업을 시행한 횟수가 된다. 이때 k-2개로 나누어떨어지지 않으면 한번 더 변경시켜야하므로 조건을 추가해주자

 

-시간복잡도-

단순 계산이므로 O(1)이된다.

 

-코드-

#include <stdio.h>
int main() {
	int arr[100000];
	int n,k,i;
	int cnt=1;
	scanf("%d %d",&n,&k);
	for(i=0;i<n;i++){
		scanf("%d",&arr[i]);
	}
	
	n-=k;
	k--;
	
	cnt+=(n%k==0?n/k:n/k+1);
	
	printf("%d",cnt);
	return 0;
}