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

✏️ 문제

 K개의 팀이 박 터트리기 게임을 한다. 각 팀은 하나의 바구니를 가지고 있고, 바구니에 들어있는 공을 던져서 자기 팀의 박을 터트려야 한다.
우리는 게임을 준비하기 위해서, N개의 공을  K개의 바구니에 나눠 담아야 한다. 이때, 게임의 재미를 위해서 바구니에 담기는 공의 개수를 모두 다르게 하고 싶다. 즉, N개의 공을  K개의 바구니에 빠짐없이 나누어 담는데, 각 바구니에는 1개 이상의 공이 있어야 하고, 바구니에 담긴 공의 개수가 모두 달라야 한다.
게임의 불공정함을 줄이기 위해서, 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이가 최소가 되도록 담을 것이다.
공을 바구니에 나눠 담기 위한 규칙을 정리하면 다음과 같다.
N개의 공을  K개의 바구니에 빠짐없이 나누어 담는다.각 바구니에는 1개 이상의 공이 들어 있어야 한다.각 바구니에 담긴 공의 개수는 모두 달라야 한다.가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이가 최소가 되어야 한다.
위의 규칙을 모두 만족하며 N개의 공을  K개의 바구니에 나눠 담을 때, 나눠 담을 수 있는지 여부를 결정하고, 담을 수 있는 경우에는 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이를 계산해서 출력하는 프로그램을 작성하시오.

 

🤖 알고리즘

 

#수학  #그리디

 

 

🤯 풀이 방법

먼저 1부터 K개까지 하나씩 늘려가면서 담는다는 가정 하에 fibonachi K를 찾아서 나눠 담을 수 없는 경우 (N이 fibonachi K보다 작은 경우) -1을 출력하여 예외처리한다.

그렇지 않은 경우 먼저 하나씩 늘려갔다는 가정 하에 N에서 fibonachi K를 뺀 수로 시작하고, 가장 적게 담은 곳은 1, 가장 많이 담은 곳은 K개가 될 것이다.

이후 전체 바구니에 하나씩 넣는 상황을 가정하여 N에서 K만큼을 빼주고, 그래도 N이 K보다 큰 경우 다시 빼준다.

그리고 남은 공의 수가 중요한데, N에서 K만큼 계속 빼고 남은 공은 N % K이다.

만약 N % K가 0인 경우 하나씩 넣다 보니 더 넣을 공이 없다는 뜻이므로 가장 큰 공과 가장 작은 공의 차이는 1과 K의 차이.

그렇지 않은 경우 1과 K의 차이 + 1 이 답이 되므로 답은 K와 같다.

 

👾 구현 코드 (파이썬)

 

처음 코드

# [BOJ] <S4> 박 터뜨리기
import sys
input = sys.stdin.readline

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

for i in range(1, K + 1):
    fn += i

if fn > N:  # 나눠 담을 수 없는 경우
    print(-1)
else:
    N -= fn
    s = 1
    b = K
    while N >= K:
        N -= K
        s += 1
        b += 1
    if N == 0:
        print(b - s)
    else:
        print(b - s + 1)

 

개선한 코드

# [BOJ] <S4> 박 터뜨리기
import sys
input = sys.stdin.readline

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

for i in range(1, K + 1):
    fn += i

if fn > N:  # 나눠 담을 수 없는 경우
    print(-1)
else:
    N -= fn
    if N % K == 0:
        print(K - 1)
    else:
        print(K)

 

19939번: 박 터뜨리기