7188 : 사탕 배분
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
N명의 사람에게 M종류의 사탕을 남김없이 배분하려고 합니다. 각 사탕 종류별 보유 수량과 각 사람이 특정 종류의 사탕을 받았을 때의 선호도가 주어집니다. 모든 사탕을 배분하여 선호도 합이 가장 적은 사람의 선호도를 최대화하는 최댓값(Max-Min)을 구하십시오.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 사람의 수 N과 사탕 종류의 수 M이 주어집니다. (1 ≤ N ≤ 4, 1 ≤ M ≤ 10)
둘째 줄에 M종류 사탕의 개수가 공백으로 구분되어 주어집니다.
셋째 줄부터 N개의 줄에 걸쳐 각 사람의 사탕 종류별 선호도 행렬(N×M)이 주어집니다.
둘째 줄에 M종류 사탕의 개수가 공백으로 구분되어 주어집니다.
셋째 줄부터 N개의 줄에 걸쳐 각 사람의 사탕 종류별 선호도 행렬(N×M)이 주어집니다.
출력 설명
배분 결과 선호도 합의 최솟값의 최댓값을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
2 2
1 1
1 2
3 4
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2도움
배분 방식에 따라 최소 선호도를 최대화한 결과값은 2입니다.