문제

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

---

풀이

처음 시도했던 방법은 N개의 공을 K개의 바구니에 나눠서 담는 모든 경우의 수를 구하고

그 중에서 바구니에 담긴 공 개수의 max - min 차이를 최소화 할 수 있는 경우를 선택하는 것이다.

그런데... N개의 공을 K개의 바구니에 분할하여 담는 모든 경우의 수를 어떻게 구해야 할지 방법이 떠오르지 않았다!!

계속 고민하다가 답을 보니까 규칙성을 찾아서 해결할 수 있는 문제였다... 🥲

1. 1 + 2 + ... + K 와 같이 연속적인 개수로 바구니에 공을 나눠 담는다고 가정한다.
   • 이 경우에 각 바구니 간의 공의 개수 차이를 1로 최소화 할 수 있다. (그리디)
2. if (바구니에 담은 공의 개수 총합 K(K+1)/2 > N) → 불가능한 경우이므로 -1 출력
3. 그렇지 않으면, 가능한 경우는 아래 두 가지밖에 없다.

6 3
1 2 3 -> 2 (K-1)

9 3
2 3 4 -> 2 (K-1)

10 4
1 2 3 4 -> 3 (K-1)

위의 예시와 같이 연속적인 수로 담을 수 있는 경우와

7 3
1 2 4 -> 3 (K)

11 3
2 4 5 -> 3 (K)

11 4
1 2 3 5 -> 4 (K)

연속적이지 않은 수로 담는 경우 이렇게 두 가지로 나뉜다.

전자의 경우: {N - K(K+1)/2} % K == 0, 정답은 K-1

{6 - (1 + 2 + 3)} % 2 = 0
{9 - (1 + 2 + 3)} % 3 = 0
{10 - (1 + 2 + 3 + 4)} % 3 = 0

후자의 경우: (N - K(K+1)/2) % K != 0, 정답은 K가 된다.

{7 - (1 + 2 + 3)} % 3 = 1
{11 - (1 + 2 + 3)} % 3 = 2
{11 - (1 + 2 + 3 + 4)} % 3 = 1

#include <iostream>
#include <string> 
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long ll; 
typedef pair<int, int> pii;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, K;
	cin >> N >> K; 

	int sum = 0; 
	for(int i = 1; i <= K; i++){
		sum += i; 
	}

	N -= sum; 

	if(N < 0){
		cout << "-1\n";
	}else{
		if(N % K == 0) cout << K - 1; 
		else cout << K; 
	}
	
	return 0;
}

그리디 + 규칙성을 파악하여 해결하는 문제였다. 실버 문제인데도 혼자서 해결하기 어려운 문제였다.