[백준] 19939 : 박 터뜨리기 - Python

그리디 알고리즘

문제해결
이 문제는 처음 생각하는게 까다로웠다. N개의 공을 K개의 바구니에 담는데 가장 큰 바구니와 가장 작은 바구니의 공의 개수 차가 최소가 되어야 한다.. 즉 공차가 1인 등차수열을 이뤄야만 공의 개수가 최소인 것이다.
그렇기에 공의 최소 개수는 K * (K+1)//2 인 것이고, 그런데 딱 떨어지지 않을 수도 있다는 것을 생각해야 한다. 그렇기에 N이 최소 개수 이상이라면 바구니 개수인 K를 기준으로 나눠 떨어진다면 가장 작은 바구니의 공의 개수를 1로 보고 가장 큰 바구니를 K로 볼 수 있게 된다.
만약 딱 떨어지지 않는다면! 가장 공의 개수가 많은 바구니부터 순차적으로 공을 1개씩 더 줄 것이므로 가장 공의 개수가 많은 바구니를 공의 개수가 K+1로 볼 수 있고 가장 공의 개수가 적은 바구니를 공의 개수가 1로 볼 수 있게 된다.

소스코드

import sys


#N개의 공 K개의 바구니
#바구니에 공 개수 모두 달라.
#가장 많이 담긴 바구니와 
# 가장 적게 담긴 바구니의 공의 개수 차이가 최소가 되도록 구현

N, K = map(int, input().split())

min_num = K * (K+1) //2   #최소한의 공 개수

if N < min_num:
    print(-1)
#최소개수보다 같거나 큰경우에서는 바구니와의 나머지 연산이 되는지 봐야해
elif (N-min_num) % K == 0: #즉 딱 떨어지게 되는 경우
    print(K-1)   #가장 큰 값은 K, 가장 작은 값은 1로 생각할 수 있어
else:   #만약 안맞아 떨어진다면 가장 큰 바구니부터 공 하나씩 추가하면 
    #가장 큰 바구니는 K+1로 생각할 수 있고 가장 작은 바구니는 1로 생각할 수 있어
    print(K)