[baekjoon] 백준 19939번(파이썬): 박 터뜨리기

문제

19939번: 박 터뜨리기

- K개의 팀이 박 터트리기 게임을 한다.

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

- 우리는 게임을 준비하기 위해서, N개의 공을 K개의 바구니에 나눠 담아야 한다.

- 이때, 게임의 재미를 위해서 바구니에 담기는 공의 개수를 모두 다르게 하고 싶다.

- 즉, N개의 공을 K개의 바구니에 빠짐없이 나누어 담는데, 각 바구니에는 1개 이상의 공이 있어야 하고, 바구니에 담긴 공의 개수가 모두 달라야 한다.

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

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

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

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

- 공의 개수를 나타내는 N과 팀의 수를 나타내는 정수 K가 주어진다.

- 나눠 담을 수 없는 경우에는 -1을 출력한다.

알고리즘

- 공의 개수와 바구니의 개수(팀의 개수)를 입력받는다.

- k개의 바구니에 들어있는 공의 개수가 1개 이상이며 전부 달라야 하기 때문에 최소 공의 개수는 공차가 1인 등차수열의 합이 된다.

- 5개 바구니에 최소 1, 2, 3, 4, 5 개수씩 들어가야 하기때문에 공차가 1인 등차수열의 합이 되는 것이다.

- 공차가 1인 등차수열의 합보다 n이 작으면 규칙에 맞지않아 -1을 출력한다.

- 공의 개수 - 공차가 1인 등차수열의 합을 뺀 값이 k의 배수이면 모든 바구니에 공차가 1인 만큼 공이 들어가게 된다. 따라서 제일 작은 수는 1이 되고 제일 큰 수는 k가 된다.

- 반대로 배수가 아니면 가장 개수가 많은 바구니 부터 하나씩 더한다고 생각하면 되므로 제일 작은 수는 1이 되고 제일 큰수 k+1이 된다.

코드

import sys

n, k = map(int, sys.stdin.readline().split())
# 공차가 1인 등차수열의 합
basket = k * (k + 1) // 2
# 공차가 1인 등차수열의 합보다 공의 개수가 작으면 나눠 담을 수 없다.
if n < basket:
    print(-1)
else:
    # 공에서 공차가 1인 등차수열의 합을 뺀 값이 k의 배수이면 최소 공의 개수 차이는 k-1이 된다.
    if (n - basket) % k == 0:
        print(k - 1)
    # k의 배수가 아니면 최소 공의 개수 차이는 k가 된다.
    else:
        print(k)

github

junjange/CodingTest