6044 : 아이템 스택 배분
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
각각 무게 제한(용량 한도)이 있는 $K$개의 스택(임시 가방)이 있고, 분배해야 할 $N$개의 아이템 무게가 주어집니다.
각 스택에는 아이템을 임의로 적재할 수 있으며, 스택에 들어가는 아이템 무게의 합은 해당 스택의 용량 한도를 초과할 수 없습니다.
스택의 용량 한도를 준수하면서 최대한 많은 개수의 아이템을 담으려고 할 때, 적재 가능한 최대 아이템 개수를 구하십시오.
[제약 조건]
• 아이템 수 $N$: $1 \le N \le 1{,}000$ (정수)
• 스택 수 $K$: $1 \le K \le 10$ (정수)
• 각 아이템 무게와 스택 용량: 자연수
각 스택에는 아이템을 임의로 적재할 수 있으며, 스택에 들어가는 아이템 무게의 합은 해당 스택의 용량 한도를 초과할 수 없습니다.
스택의 용량 한도를 준수하면서 최대한 많은 개수의 아이템을 담으려고 할 때, 적재 가능한 최대 아이템 개수를 구하십시오.
[제약 조건]
• 아이템 수 $N$: $1 \le N \le 1{,}000$ (정수)
• 스택 수 $K$: $1 \le K \le 10$ (정수)
• 각 아이템 무게와 스택 용량: 자연수
입력 설명
첫째 줄에 아이템 수 $N$과 스택 수 $K$가 공백으로 구분되어 주어집니다. ($1 \le N \le 1,000$, $1 \le K \le 10$)
둘째 줄에 $N$개 아이템의 무게가 공백으로 구분되어 주어집니다. (각 무게는 자연수)
셋째 줄에 $K$개 스택의 개별 용량 한도가 공백으로 구분되어 주어집니다.
둘째 줄에 $N$개 아이템의 무게가 공백으로 구분되어 주어집니다. (각 무게는 자연수)
셋째 줄에 $K$개 스택의 개별 용량 한도가 공백으로 구분되어 주어집니다.
출력 설명
스택들의 용량 한도 내에 최대한 담을 수 있는 아이템의 최대 개수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 2
10 20 30 40 50
50 50
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3도움
적재 개수를 최대화하기 위해 그리디(Greedy) 기법을 사용합니다. 아이템 무게를 오름차순으로 정렬한 뒤, 가장 가벼운 아이템부터 용량 여유가 있는 최적의 스택에 배정합니다.