[BOJ 19939, Python 3] 박 터뜨리기

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

19939번: 박 터뜨리기

 

풀이

같은 문제: https://www.acmicpc.net/problem/1789

 

1789 문제랑 풀이 방식이 똑같습니다.

각 바구니에 담긴 공의 개수가 서로 달라야하니 1개, 2개, 3개, ... 이렇게 넣어줍니다.

이랬는데 비어있는 바구니를 발견하면 -1을 출력하고, 그게 아니라면 공을 다 사용하거나 몇 개가 남았을 겁니다.

여기서 이제 몫과 나머지를 이용하여 문제를 풀면 됩니다.

 

상황1)

만약 4개의 바구니에 공이 [1개, 2개, 3개, 4개]가 있고, 남은 공 4개가 있다고 해봅시다.

규칙에 맞게 공을 분배하는 방법은 여러가지가 있겠지만 최적의 방법은 [2개, 3,개, 4개, 5개]처럼 바구니에 공 1개씩 주는 것입니다. 이러면 답이 3으로 최소가 됩니다.

 

상황2)

만약 이번엔 같은 상황에서 남은 공이 2개가 있다고 해봅시다.

규칙에 맞게 공을 분배하는 방법은 1개, 2개, 3개에 공을 1개 줄 수 없으니 4개 있는 곳에 1개를 줍니다.

이러면 [1개, 2개, 3개, 5개]가 되고 남은 공은 1개 입니다.

나머지 1개는 공이 3개 있는 바구니나, 공이 5개 있는 바구니에 한 개를 줄 수 있습니다. 우리는 최솟값을 구해야하니까 공이 3개 있는 바구니에 공을 1개 넘겨줄 수 있습니다.

이렇게 되면 [1개, 2개, 4개, 5개]로 답은 4로 주어진 상황에서 구할 수 있는 최솟값입니다.

 

이제 큰 수를 넣어봅시다.

4개의 바구니에 공이 [1개, 2개, 3개, 4개]가 있고, 남은 공 563개가 있다고 해봅시다.

563보다 작은 4의 배수중 가장 큰 수는 560입니다. 상황1처럼 140개씩 각 바구니에 넣어줍니다.

[141개, 142개, 143개, 144개]이고 남은 공은 3개 인데, 상황2처럼 왼쪽 바구니부터 1개씩 넣어줍니다.

[141개, 143개, 144개, 145개]가 되고 답은 145 - 141 = 4가 됩니다.

 

이것을 통해 남은 공이 바구니의 개수 K의 배수라면 답은 N-1이 되고, K배수가 아니라면 답은 N이 된다는 것을 알 수 있게 됩니다.

 

 

코드

n, k = map(int, input().split())
if 2 * n < k * (k + 1):
    print(-1)
    exit()
x = n - k * (k + 1) // 2
print([k, k - 1][x % k == 0])