어떤 생산품 p를 생산하는데 N개의 각기다른 아이템이 각각 r_i개씩 요구 된다고 할 때,

10개의 칸을 선택해서 최대한 많은 갯수의 p를 생산하는게 문제입니다.

먼저 모든 경우의 수를 다 해보는 경우는 다음과 같습니다.
i번째 아이템이 각 칸마다 a_1, a_,2 ..., a_n_i개 주어질 때, 내림 차순으로 정렬해 놓습니다.

그 후,

10개의 주어진 자동 생산 슬롯을 어떻게 N개의 아이템에 배분 할 까가 주어진 문제인데.. 일단 모든 경우의 수는

10개의 사물 간에 N-1개의 칸막이를 치는 경우의 수와 같으므로 9 C N-1 같습니다. 이 경우를 다 해본 뒤 생산되는 아이템의 최대 수가 정답입니다.

이 것보다 더 빠르게 할 수 없느냐를 생각중인데..

일단 N=2인 경우에는 각 아이템을 내림차순 정렬 해 놓고,
먼저 한개씩 배분은 해야 하므로 2개의 슬롯을 배분 합니다. 그 후는 greedy 하게 하나의 아이템의 (총 갯수/생산에 필요한 갯수) 의 정수가 서로 다를 때 슬롯을 작은쪽 아이템에게 그리디하게 배분하면 되는데.

이게 N >= 3 이상인 아이디어에도 일단 한개씩 배분해놓고 비슷하게 (총갯수/생산에 필요한 갯수)의 정수값이 최소인 아이템을 우선순위로 슬롯을 하나씩 배분하면 되는지를.. greedy하게 증명 하기가 애매해서 질문드립니다.

그것만 증명하면 힙같은 자료구조로 풀면 10 log N에 풀 수 있을 것 같은데 말입니다...
----------------- 품-----
스포:

위 처럼도 풀수잇고.. greedy/이분법으로도 풀수잇네요. 저는 greedy로만 품.