BOJ 19939 - 박 터뜨리기 (Python)

S4, Greedy

풀이

간단하게 생각하면
바구니의 수 만큼 등차수열을 이루면 된다.

• 따라서 등차수열의 총합공식 = n(n+1)/2 보다 주어지는 공의 수 가 적으면 -1
  K * (K + 1) // 2 > N
• 공의 수의 배수가 바구니의 수와 같다면 K-1
  • ex) 공이 6개 바구니가 3개
    2/2/2 → 1/2/3 즉, K - 1
• 다르다면, 어차피 가장 공이 많은 바구니에 공을 담아야 하므로 K
  • ex) 공이 7개 바구니가 3개
    1/2/3 → 1/2/4 (2/2/3인 경우 조건에 위반되므로)

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

tmp = K * (K + 1) // 2
if tmp > N:
    print(-1)
else:
    if (N - tmp) % K == 0:
        print(K - 1)
    else:
        print(K)

등차수열의 총합을 구하는 공식을 까먹고 있었다.