jetalog.net

문제

알고리즘 에듀 학생들은 코치가 나눠주는 마시멜로를 받기 위해 반별로 학생들이 줄을 서 있다.

알고리즘 에듀는 Q개의 반으로 운영되고 있으며, 각각의 반에 해당하는 학생수는 N_i명이다.

학생들은 본인이 원하는 만큼의 마시멜로를 얻으면 행복해지고 줄을 빠져나간다.
각 줄의 맨 앞에 있는 학생에게만 마시멜로를 줄 수 있으며, 마시멜로를 받은 학생이 빠져나가면 다음 학생이 앞으로 올 수 있다.

K명의 학생들을 행복하게 만들기 위해 필요한 최소 마시멜로의 숫자를 구하는 프로그램을 작성하시오 .  

입력

첫 줄에는 반의 수 Q(1<= Q<= 1,000) 와 만족시켜야할 학생의 수 K(1<= K <=1,000,000)를 공백을 두고 입력한다.

각각의 반에 대해 첫째 줄에는 각 반의 학생 숫자 N(1<= N <= 100) 를 입력하고,
두번째 줄에 각 학생들이 원하는 마시멜로의 개수를 나타내는 정수 M(1 <= M <= 10,000)을 공백을 두고 입력한다.

출력

필요한 최소 마시멜로의 개수를 출력한다.

만약 만족시켜야할 학생 수가 줄 서있는 학생수 총 합보다 더 클 경우, 줄 서있는 학생들 모두를 만족시키는 마시멜로의 개수를 출력한다.  

입력 예시 1

4 9
3
1 2 3
1
8
2
2 5
3
1 4 6

출력 예시 1

32

입력 예시 2

4 8
3
1 2 3
1
8
2
2 5
3
1 4 6

출력 예시 2

24

코드

Java

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
 
        int classCnt, targetCnt, totalCnt = 0;
 
        classCnt = scan.nextInt();
        targetCnt = scan.nextInt();
 
        Queue<Integer>[] classes = new LinkedList[classCnt];
        for (int i = 0; i < classCnt; i++) {
            Queue<Integer> queue = new LinkedList<>();
 
            int studentCnt = scan.nextInt();
            totalCnt += studentCnt;
 
            for (int j = 0; j < studentCnt; j++) {
                queue.add(scan.nextInt());
            }
 
            classes[i] = queue;
        }
 
        long givenCnt = 0;
        int satisfiedStudents = 0;
        while ((satisfiedStudents < totalCnt) && (satisfiedStudents < targetCnt)) {
            int classNo = 0;
            int marshmallow = Integer.MAX_VALUE;
 
            for (int i = 0; i < classCnt; i++) {
                if ((0 < classes[i].size()) && (classes[i].peek() < marshmallow)) {
                    classNo = i;
                    marshmallow = classes[i].peek();
                }
            }
 
            classes[classNo].remove();
            givenCnt += marshmallow;
            satisfiedStudents++;
        }
 
        System.out.println(givenCnt);
    }
}