테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 박 터뜨리기 ======

===== 풀이 =====
  * 우선, K개의 바구니에 서로 다른 갯수의 공을 넣으려면, 최소 1+2+...+K = K*(K+1)/2 = M개의 공이 있어야 한다. N이 이것보다 작으면 불가능하니 -1 을 출력한다
  * 이제 M 개의 공을 저렇게 넣었을때, 남은 N-M개의 공을 최대한 골고루 넣어야 바구니의 공의 갯수 차이를 최소화할수 있다. N-M을 K로 나눈 몫과 나머지가 a와 b 라면, 각 바구니에 a개씩 넣어주고, 남은 b개는 가장 많이 들어있는 바구니에서부터 하나씩 넣어주면 된다. 
  * 그러면 가장 적게 든 바구니에는 1+a개가 들어있고, 가장 많이든 바구니에는 b>0이면 K+a+1, b=0 이면 K+a개가 들어가게 된다
  * 시간복잡도는 O(1)

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 19939. 박 터뜨리기".

- Problem link: https://www.acmicpc.net/problem/19939
- Solution link: http://www.teferi.net/ps/problems/boj/19939
"""


def main():
    N, K = [int(x) for x in input().split()]

    t = N - K * (K + 1) // 2
    if t < 0:
        print('-1')
    elif t % K == 0:
        print(K - 1)
    else:
        print(K)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:실버_4}}