백준 BOJ 19939 - 박 터트리기

예선 1번.

이게 난 2번보다 빡셌던거같은데...?

 

바구니에 나눠 담지 못하는 경우는

차이가 전부 1임에도 불구하고 공이 부족한 경우이다.

즉 계단모양으로 배열하면 되고,

공의 갯수가 계단모양의 넓이보다 작으면 -1을 출력해주면 된다.

 

이제 계단모양으로 일단 공을 배열해놓고,

계단의 가장 윗층부터 공을 올려놓으면서

한계단씩 내려오는게

공의 개수차이를 가장 작게 하는 배치 방법이다.

그대로 구현만 해주면 AC.

 

#include <stdio.h>

int arr[1234] = {0};

int main(){
	int n,k;
	scanf("%d %d", &n, &k);
	
	if(n < k*(k+1)/2){ printf("-1"); return 0; }
	for(int i=1; i<=k; i++){ arr[i] = i; n-=i; }
	
	int ptr=k;
	while(n){
		arr[ptr]++;
		ptr--;
		n--;
		if(ptr==0) ptr = k;
	}
	printf("%d", arr[k]-arr[1]);
	return 0;
}