(JAVA) 백준 2878번 : 캔디캔디

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

2878번: 캔디캔디

 

착한 제목에 그렇지 못한 문제..

 

이진탐색 보다는 탐욕에 가까운 문제로

 

골머리 한시간 썩히다가 해설을 참고하니

 

그리디로 더 쉽게 풀 수 있었다.

 

 

 

 

 

 

핵심

---

  -  못 주는 사탕의 개수는 고정되어 있다.

 

M개의 사탕을 줄 수 있고, 각 사람들이 원하는 사탕의 개수 총합을 SUM 이라고 할 때

 

  못 주는 사탕의 개수 = SUM - M

 

 

 

  -  위에서 못주는 사탕의 개수로 공략한다. 이 때, 분노게이지를 낮추기 위해선 한 사람한테 못주는 사탕의 개수를 쏠리게 하지 않고, 골고루 적게 못줘야 한다.

  

  이는 곧, 더 많이 요구하는 사람들에게는 남들보다 더 많이 주고, 조금 요구하는 사람들에게는 조금 줘서 못주는 사탕의 개수를 비슷하게 유지하는 것이다. (이것이 민주주의?)

 

 

 

  -  위처럼 봐가면서 나눠주기 위해서는 어떻게하냐?

  

  못 주는 사탕의 개수를 선택하라고 한다. 

    ->  math.min(요구하는 사탕의 개수, 남은 사탕 개수 / 아직 나눠주지 않은 사람 인원)

    ->  즉, 너가 요구하는 개수만큼 못받을래? or 남은 사람들끼리 똑같이 못받을래?

    *** 단, 조건은 해당 배열을 오름차순 정렬해둬야 한다.  요구 개수가 적은 사람들을 그만큼 먼저 나눠주기

 

 

 

  -  조건 범위 상 전부 long 타입으로 진행해야 한다. 

 

 

 

  -  Math.pow() 같은 경우는 (long) 으로 앞에 형변환을 진행해야 한다.

 

 

 

  -  잊지않고 2^64를 나눈 나머지로 출력하기!

 

 

 

 

그럼 문제를 해결하실 수 있습니다.

 

더 궁금한 사항이 있으면 소스코드 참고해주시고, 댓글 달아주세요!

 

감사합니다.

 

소스코드

---