31508번: Candy Factory

\(\displaystyle i\)번째 공장에서 제공한 캔디 개수를 \(\displaystyle a_{i}\)라고 하자.

관찰 1: 추가해야하는 캔디 개수의 최솟값을 \(\displaystyle x\)라고 하면, \(\displaystyle x+\sum\limits _{i=1}^{n} a_{i}\)는 \(\displaystyle k\)의 배수가 되어야 한다.

관찰 2: \(\displaystyle a_{1} \geq a_{2} \geq a_{3} \geq \ \cdots \ \geq a_{n}\)이 되도록 재배치 해도 구하려는 값 \(\displaystyle x\)의 값은 변하지 않는다.

관찰 3: \(\displaystyle a_{k+1} ,\ a_{k+2} ,\cdots ,\ a_{n}\) 중에서 서로 다른 \(\displaystyle t\)개와 \(\displaystyle a_{1} ,\ a_{2} ,\cdots ,\ a_{k}\) 중에서 서로 다른 \(\displaystyle k-t\)개를 하나의 팩으로 만들 수 있다.

관찰 4: 위 문장을 다시 생각해보면, \(\displaystyle k+1\)번째 이상 공장의 캔디를 \(\displaystyle k\)번째 이하 공장 캔디에 채워 넣어도 상관 없다.

풀이: 최소 \(\displaystyle a_{1}\)개의 팩을 만들어야하므로, \(\displaystyle k\cdot a_{1} -\sum _{i=1}^{n} a_{i}\)이 \(\displaystyle 0\) 이상일 경우에는 답이고, \(\displaystyle 0\) 미만일 경우에는 \(\displaystyle 0\) 이상이 될 때까지 \(\displaystyle k\)를 더해준 값이 답이다.