[python/파이썬] 백준 19939 박 터뜨리기

문제

 K$K$개의 팀이 박 터트리기 게임을 한다. 각 팀은 하나의 바구니를 가지고 있고, 바구니에 들어있는 공을 던져서 자기 팀의 박을 터트려야 한다.

우리는 게임을 준비하기 위해서, N$N$개의 공을 K$K$개의 바구니에 나눠 담아야 한다. 이때, 게임의 재미를 위해서 바구니에 담기는 공의 개수를 모두 다르게 하고 싶다. 즉, N$N$개의 공을 K$K$개의 바구니에 빠짐없이 나누어 담는데, 각 바구니에는 1개 이상의 공이 있어야 하고, 바구니에 담긴 공의 개수가 모두 달라야 한다.

게임의 불공정함을 줄이기 위해서, 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이가 최소가 되도록 담을 것이다.

공을 바구니에 나눠 담기 위한 규칙을 정리하면 다음과 같다.

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

위의 규칙을 모두 만족하며 N$N$개의 공을 K$K$개의 바구니에 나눠 담을 때, 나눠 담을 수 있는지 여부를 결정하고, 담을 수 있는 경우에는 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이를 계산해서 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에 공의 개수를 나타내는 N$N$과 팀의 수를 나타내는 정수 K$K$가 주어진다.

출력

 N$N$개의 공을 K$K$개의 바구니에 문제의 규칙을 만족하면서 나눠 담을 수 있다면, 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이를 출력한다. 나눠 담을 수 없는 경우에는 -1을 출력한다.

제한

•  2≤N≤100,000$2 \le N \le 100,000$ 
•  2≤K≤1,000$2 \le K \le 1,000$ 

예제 입력 1 복사

5 3

예제 출력 1 복사

-1

예제 입력 2 복사

6 3

예제 출력 2 복사

2

 

[문제 풀이]

 

n개의 공과, k개의 바구니가 있을 때

모든 바구니에 공을 넣고, 바구니에 들어있는 공의 개수는 바구니마다 달라야 한다.

 

k개의 바구니가 있을 때 위의 조건을 만족하기 위해서 필요한 공의 개수는 최소 1+2+3+4+ ... + k 개다.

1부터 k까지 1씩 증가하는 수들의 합으로 

k*(k+1)/2로 나타낼 수 있다.

 

공의 개수가 k*(k+1)/2보다 작다면 모든 바구니에 다른 개수의 공을 넣는 것이 불가능하다.(조건을 만족하는 최소 공의 개수이기 때문)

 

공의 개수가 k*(k+1)/2보다 클 때

 

공의 개수 - k*(k+1)/2의 값이 몇이냐가 정답을 결정짓게 된다. 이 값을 a라고 하면

a가 k(바구니 개수)의 배수라면 모든 바구니에 동일한 개수만큼 공을 더 넣어주면 되기에

가장 적은 공의 개수와 가장 많은 공의 개수 사이의 차는 변하지 않는다 (k-1)

 

만일 a가 k의 배수가 아니라면 a%k 는 1부터 k-1 사이의 값이 될 것이다. 

이 경우 가장 개수가 많은 바구니부터 적은 바구니 순으로 공을 하나씩 추가해주면 가장 개수가 적은 바구니에는 공이 추가되지 않는다.

(모든 공의 개수를 다르게 하기 위함)

따라서 가장 적은 공의 개수와 가장 많은 공의 개수 사이의 차는 k가 된다.

 

ex1)

n = 30

k = 5

 

k*(k+1)/2 = 15

 

30 > 15

 

4 / 5 / 6 / 7 / 8

8 - 4 = 4 => k-1 = 5

ex2)

n = 18

k = 5

 

k*(k+1)/2 = 15

 

18 > 15

 

1 / 2 / 3 / 4 / 5

이 상태에서 남은 3개의 공을 오른쪽 바구니부터 하나씩 채워줘야 다른 공과 개수가 겹치지 않는다.

1 / 2 / 4 / 5 / 6

 

6 - 1 = 5 => k = 5

 

 

[소스 코드]

n, k = map(int, input().split())

check = k*(k+1) //2

if n < check:
    print(-1)
elif (n - check) % k == 0:
    print(k-1)
else:
    print(k)