[백준 2792번] 보석 상자- java

문제 설명

1. 인원수 N, 보석의 색깔수 M이 주어진다.

2. M가지 색에 대해 각각의 개수가 주어진다.

3. 이 M개의 보석을 N명의 학생에게 나누어 줄 때, 모든 인원에게 나누어 줄 수 있는 최소 보석 개수를 구해주면 될것이다.

 

풀이 과정

 1. 이분탐색이 어려워서 공부하기 위해 하나 더 풀어보았다. 이전문제에서 공부했어서 풀이 자체는 금방 도출했는데... 이번에는 뭔가 구현이 어려웠다. 더 풀어봐야 할 것 같다.

 2. 중요한 값들에 대해 이야기하자면

      A. 주어지는 보석개수의 차이가 아니라 개수 자체에 관한 문제라는것 -> 그냥 보석을 N명에게 모두 나누어 줄 수 있는 최소개수를 가지면 된다.

      B. 아예 보석을 못받는 학생이 있어도 괜찮다는것 -> 학생수보다 주는보석방법의 개수가 작거나 같으면 싹다 답이 될 수 있다는것.

    이다.

 3. 왼쪽 구하는 방법 -> 작은 수 왼쪽은 1부터 시작하면 된다. 보석을 나누어주는것이니까.

 4. 오른쪽 구하는 방법 -> 큰 수 오른쪽은 최대 보석의 개수를 가지면 된다. 그 이상 줘도 줄 수 있는 개수는 바뀌지 않으므로 메모리 낭비이다.

 5. 왼쪽, 오른쪽 값이 정해졌으므로 그 가운데 mid에 대해 해당 크기에 맞추어 보석을 하나하나 나눠준다.

 6. 현재 나눠준 보석이 학생 수보다 많으면 -> 모두 준게 아니므로 이방법은 못쓴다. 더 많이 나눠줄것.

 8. 현재 나눠준 보석이 학생 수보다 적거나 같으면 -> 못받는 학생이 있어도 괜찮다. 일단 저장하고 더 적게 줄 수 있는 방법을 찾아볼것.

 9. 중요한 것은, 모든 학생에게 나눠줘야하는것이 아니다!

 10. 일단 남는 보석이 없다면 저장하고, 한번에 그보다 적은 보석을 나눠주는 방법을 찾아가면 된다.

 

코드