19939번: 박 터뜨리기 (수학)

19939번: 박 터뜨리기

간단한 수학문제이다. 바구니가 k개, 공이 n개인데 최소한 1개 들어가야하고 바구니 속 공의 개수는 다 달라야한다. 

1. 공의 개수의 최소는 높이가 1,2,3,..,k일 때 이므로 k(k+1)/2 > n 이면 불가능. 
2. n-k(k+1/2)는 1,2,3,..,k 개를 만들고 남은 공의 개수, 이때 가장 많은 공의 개수와 가장 적은 공의 개수의 차는 k-1개가 나올 수 있는 가장 최소임. 이때의 조건은 a+1,a+2,a+3,...,a+k, 즉 남은 공의 개수가 k의 배수일 때 가능하다. 
3. 2,번 경우가 아닐 때 a+1,a+2,a+3,...,a+k가 되게 만들면 남은 공의 개수는 (n - k(k+1)/2) mod k 인데 현재 높이가 a+1~a+k 로 연속한 상태이므로,  남은 공의 개수가 i (0<i<k) 이면 어떤 하나의 바구니에 i개를 몽땅 부어서 a+k+1을 만들 수 있음. 즉 이때는 k개가 최대와 최소의 차이이다.

n,k = map(int,input().split())
if k*(k+1) > 2*n: print(-1)
elif (n-k*(k+1)/2)%k==0: print(k-1)
else: print(k)

블로그 글을 올릴 때 그냥 올리고 싶은거 무작정 올리는 것 같아서 앞으로는 다시 볼 필요가 있는 것, 새롭게 푼 아이디어, 어려워 하는 것 등을 중심으로 올려야겠다.