[백준 19939번-파이썬/Python] 박 터뜨리기

http://acmicpc.net/problem/19939

{코드}

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

{설명}

K개의 바구니에 들어있는 공의 개수가 1개 이상이며 전부 달라야 하기 때문에 공의 최솟값은 k(k+1)/2이다.

그림처럼 각 바구니가 순서대로 공의 개수가 결정된다면 전의 바구니보다 1개 더 많을 때가 최소이기 때문이다.

그렇다면 최솟값보다 공의 개수가 적으면 -1을 반환하면 된다.

공의 개수가 더 많을 경우 1부터 n까지 세우고 남은 공의 개수를 생각해보자.

만약 공의 개수가 바구니의 수와 맞아 떨어진다면 각각 (남은 공의 개수)/(바구니 수)를 각 바구니에 더한 것과 같으므로 무시하면 된다.

그러면 가장 개수가 적은 바구니(1)과 가장 개수가 많은 바구니(k)의 차인 k-1을 반환한다.

바구니의 수와 맞아떨어지지 않으면 가장 개수가 많은 바구니부터 하나씩 더한다고 생각하면 되므로 가장 개수가 적은 바구니(1)와 가장 개수가 많은 바구니(k+1)의 차인 k를 반환한다.