백준 19939 파이썬

https://www.acmicpc.net/problem/19939

19939번: 박 터뜨리기

 

import sys

if __name__ == '__main__':
    N, K = map(int, input().split())
    condition_ball = 0
    for i in range(1, K + 1):
        condition_ball += i

    if N < condition_ball:
        print(-1)
    else:
        if (N - condition_ball) % K == 0:
            print(K - 1)
        else:
            print(K)


# 22 4
# 답: 3

 

문제 조건은 아래와 같다.

1.  N개의 공을 K개의 바구니에 빠짐없이 나누어 담는다.
2. 각 바구니에는 1개 이상의 공이 들어 있어야 한다.
3. 각 바구니에 담긴 공의 개수는 모두 달라야 한다.
4. 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이가 최소가 되어야 한다.

위 조건을 만족하기 위해서 최소로 필요한 공의 갯수를 먼저 알아야 한다.

K=5 즉, 박이 5개라고 가정했을 때

 

각 박에 1 - 2 - 3 - 4- 5 와 같이 담을 경우 공의 최소 요구 갯수가 된다. 

 

바구니 수만큼 순회하면서 1씩 증가한 값을 누적시켜주면 최소 요구  갯수를 알 수 있다.

 

최소 요구 갯수를 구한 후, N 에서 최소갯수를 뺏을때 남은 공이 박의 갯수로 나눠떨어지면 각 박에 균등하게 추가해주면 되므로 

1-2-3-4-5 처럼 1부터 순차적으로 담은것과 결과가 다를게 없다.

그러므로 이 경우엔 K(박의 수) - 1 (최소로 담은 공) 을 해주면 된다.

 

 

최소 요구 갯수를 구한 후, N 에서 최소갯수를 뺏을때 남은 공이 박의 갯수로 나눠떨어지지 않는 경우,

 

각 박에 차례로 하나씩 넣어준다고 가정하면 되므로 최대값이 +1 된다.

그러므로 이 경우엔 K(박의 수) - 1 (최소로 담은 공) + 1(하나씩 추가한 남은공) = K 을 해주면 된다.