문제 링크: https://www.acmicpc.net/problem/19939

Thumbnail: Photo by Michelle Garres (Unsplash)

문제를 처음 봤을 때에는 풀이가 바로 떠오르지 않았지만, 차근차근 생각해보니 간단한 형태로 풀이를 정리해낼 수 있었습니다!

생각한 과정

이해에 도움이 되지 않을까 하여, 제가 생각한 과정을 남겨두겠습니다.

\(K\)개의 바구니에 \(N\)개의 박을 나눠 담는데, 각 바구니에 담긴 박의 개수가 모두 달라야 합니다. 이 경우, 가장 간단하게 생각할 수 있는 경우는 1번 바구니부터 \(K\)번 바구니까지 1씩 증가하는 계단식 형태로 박을 나눠 담는 것입니다.

사실 조금만 고민해봐도 1씩 증가하는 형태로 나눠 담을 수 없다면 필연적으로 둘 이상의 바구니에 같은 개수의 박을 담게 됩니다.

그렇다면, 1씩 증가하는 형태로 \(K\)개의 바구니에 박을 나눠 담은 뒤를 생각해 봅시다. 만약 박이 깔끔하게 나눠 떨어졌다면, 가장 많이 담은 바구니와 가장 적게 담은 바구니의 박 개수 차이는 \(K - 1\)일겁니다.

하지만 대부분의 경우 남아있는 박이 존재할 겁니다. 이를 \(R\)이라고 하겠습니다.
\(R > 0\)이라면, 남아 있는 박을 K개로 균등히 나눠 담고도 남는게 있는지 확인해봅시다. 이미 1~K로 바구니에 박을 담아 두었으니, 균등히 나눠 담아도 여전히 각 바구니의 박의 개수는 서로 다릅니다.
\(R \mod K = 0\), 즉 균등히 나눠 담았을 때 딱 나눠 떨어진다면 여전히 가장 많이 담은 바구니와 가장 적게 담은 바구니의 박 개수 차이는 \(K - 1\)입니다.

\(R \mod K > 0\), 즉 균등히 나눠 담았을 때도 남는 박이 있다면 남은 박은 가장 많이 담아둔 바구니부터 역순으로 1개씩 나눠 담는다고 생각해봅시다. 지금 상황에서 남아 있는 K개보다 적게 남았을 것이며, 그러므로 가장 적게 담긴 바구니에는 담을 박이 없을 것입니다. 따라서, 가장 많이 담은 바구니에는 박이 하나 더 늘었지만 가장 적게 담은 바구니는 그대로이므로 이 둘의 박 개수 차이는 \(K\)입니다.

풀이

\(N\)개의 박을 \(K\)개의 바구니에 서로 다른 개수로 나눠 담으려면, 1번 바구니부터 \(N\)번 바구니까지 1씩 증가하는 형태로 먼저 나눠 담고 그 나머지가 있는지 판단하면 됩니다. 이때, 1씩 증가하는 형태로 나눠 담는 것은 등차수열의 합 계산식으로 구할 수 있습니다.

결국 1~K번 바구니에 등차수열 꼴로 나눠 담은 박의 개수의 합이 N보다 작으면 박을 서로 다른 개수로 나눌 수 없는 것이고, N보다 같거나 클 경우 추가로 아래 과정을 거치면 됩니다 :

나머지 \(R = N - (K \times (K+1) \div 2\)이

• \(R \mod K = 0\) : 가장 많이 담은 바구니와 가장 적게 담은 바구니의 개수 차이는 \(K-1\)개
• \(R \mod K > 0\) : 가장 많이 담은 바구니와 가장 적게 담은 바구니의 개수 차이는 \(K\)개

전체 코드

N, K = map(int, open(0).readline().split())

base = K * (K+1) / 2
if base > N:
    print(-1)
else:
    leftovers = (N - int(base)) % K
    # 1부터 계단식으로 K개를 먼저 바구니에 넣고 남은 개수가 있다면, 이를 최대한 K개로 고르게 나눠서 배분한다.
    # K개의 바구니에 나머지를 고르게 배분하고도 남았다면, 이는 가장 많은쪽 바구니부터 역순으로 1개씩 배분한다 (K개에 전부 1개씩은 못두는 상황이므로)
    # 이때의 바구니의 개수 차이는 (K+diff) - (1+diff) + (1 if leftovers % K > 0 else 0)              
    print(K if leftovers > 0 else K - 1)

시행착오

​처음에는 1~K의 바구니를 배열로 구현해보기도 했으나, 곧 굳이 메모리에 저장할 필요 자체가 없음을 깨닫고 코드를 개선했습니다. 1씩 증가하는 형태로 바구니에 담는 것도 반복문으로 구현했었으나, 등차수열의 합 공식으로 계산하는 형태로 개선했습니다.