[BOJ] 19939 박터뜨리기(python)

문제

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

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

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

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

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

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

입력

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

출력

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

풀이

생각보다 그렇게 어렵게 느껴지진 않았다.
모든 바구니에 담긴 공의 갯수가 달라야하고, 최소 1개의 공을 담아야하니 만약 5개의 바구니면 최소 갯수의 공을 조건에 맞게 담으려면 1, 2, 3, 4, 5개씩 담아야한다.
간단하게 등차수열로 생각하면 되니 n(n+1)/2개를 필요한 공의 최소 갯수로 생각했고, 그 후 가장 많이 담긴 바구니부터 순차적으로 하나씩 공을 추가하면 최소값과 최대값의 차이가 가장 작아진다고 생각하고 풀었다.

import sys

num_balls, num_teams = map(int, sys.stdin.readline().split())
# 각 바구니에 조건 맞게 공 담는데 필요한 최소 공 갯수
min_balls = num_teams*(num_teams+1)/2

# 최소 갯수보다 공이 모자라면 -1 return
if min_balls > num_balls:
   print(-1)
else:
	# 조건에 맞춰서 공 담아줌
   teams = [i for i in range(num_teams-1, -1, -1)]
   num_balls -= min_balls
   while num_balls > 0:
   	공 있는 동안 많이 담긴 바구니부터 공 배분
       for i in range(num_teams):
           if num_balls == 0:
               break
           teams[i] += 1
           num_balls -= 1
	# 이미 정렬된 상태이므로 인덱스로 접근해서 출력
   print(teams[0]-teams[-1])