문제 정보
플랫폼 : 백준
분류 : 그리디 알고리즘
난이도 : 실버3
링크 : https://www.acmicpc.net/problem/12018
입력 데이터와 시간제한 검증
입력 데이터 갯수 : 10000개가량 (최대 과목수 100 * 최대 수강인원 100 + 기타정보)
O(nlogn) 풀이 : 시간제한 ok (정렬 사용)
자료형 : 최대 마일리지 100, int 사용가능
풀이
1 > 만약 기존에 신청한 인원 수 (배열의 수)가 수강인원(Li)보다 작다면, 1점만 리스트에 저장한다.
2 > 과목마다 내림차순으로 정렬한다.
2-1 > 수강인원(Li)번째 사람만큼의 마일리지만 넣으면 수강신청이 되므로, 해당 마일리지를 리스트에 저장한다.
3 > 리스트를 오름차순으로 정렬하여, 0번부터 마일리지를 합하여 주어진 마일리지(m)에 도달하기 전까지의 갯수를 출력한다.
ArrayList와 Array 어떤 것을 사용해도 무관하다.!
우선, 그림으로 풀이과정을 보자.
기본적인 Input Data이다. 여기서 for문을 통해 1번을 수행해주자.
과목 1,2,3,5는 내림차순 정렬이 됐고, 과목4는 신청인원<최대인원 이므로 1점만 부여했다.
각 과목별로 최대인원번째 학생의 점수만 넣으면 수강신청 할 수 있으므로, 최대인원번째 학생을 해당 과목의 최소 점수(마일리지)로 넣었다. (문제에 마일리지가 같다면 성준에게 우선순위가 있다고 함.)
최소 점수를 오름차순으로 정렬했다. 이제 합을 구하면서, 보유한 마일리지 76점보다 낮으면 된다. 과목 4까지 더했을 때 60점이고, 5까지 더하면 86점이므로, 최대 4개까지 수강 가능하다.
이제 구현을 해보자.
각 데이터의 입력을 받아준다.
위 설명의 순서대로 코드만 작성해주면 끝!
코드
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 과목 수
int m = sc.nextInt(); // 주어진 마일리지
int[] minArr = new int[n]; //각 과목별로 수강신청 하기위해 필요한 최소 마일리지 목록
for(int i = 0; i < n; i++) {
int p = sc.nextInt(); // 과목에 신청한 사람 수
int l = sc.nextInt(); // 과목당 수강인원
Integer[] mList = new Integer[p]; // 이미 신청한 사람들의 마일리지, 내림차순 위해 Integer[]선언
for(int j = 0; j < p; j++) {
mList[j] = sc.nextInt();
}
//1. 만약 기존에 신청한 인원수 < 수강인원 Then, 1점을 리스트에 저장
if(p < l) {
minArr[i] = 1;
continue;
}else {
//2. 과목마다 내림차순 정렬
Arrays.sort(mList, Collections.reverseOrder());
//2-1. 수강인원(l)번째 사람만큼의 마일리지만 넣으면 수강신청이 됨. 해당 마일리지 리스트에 넣기
minArr[i] = mList[l-1];
}
}
//3. 리스트를 오름차순 정렬, 0번째부터 마일리지의 합 < 주어진 마일리지(m) 까지 갯수 출력
Arrays.sort(minArr);
int cnt = 0; // 수강신청 가능한 갯수
int mSum = 0; // 0번째부터 마일리지의 합
for(int i = 0; i < n; i++) {
mSum += minArr[i];
if(mSum > m) {
break;
}
cnt++;
}
System.out.println(cnt);
}
}
더 많은 정답 코드
블로그를 쓰기 이전에 풀어본 문제들이 많다. 해설강의는 없지만, 백준 문제의 풀이 코드가 필요한 경우 이곳을 클릭하여 소스코드를 참조해보도록 하자. 단, 코드만 복사-붙여넣기 하는것은 본인에게 결코 도움이 되지 않는다. 반드시 먼저 생각해보고, 막히는 경우에 참고하고 왜 이렇게 코드가 작성됐는지를 다시 한 번 생각해보는 습관을 들이자.
