티스토리 뷰

PS/boj

boj)12018 - Yonsei TOTO

kingsubin 2020. 8. 31. 18:06
import java.io.*;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int ans = 0;

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 과목 수
        int m = Integer.parseInt(st.nextToken()); // 내 마일리지
        int[] minimum = new int[n]; // 과목을 얻기 위한 최소 마일리지 배열

        // 전체 과목 루프
        for (int i = 0; i < n; i++) {

            // 과목당 루프
            st = new StringTokenizer(br.readLine());
            int people = Integer.parseInt(st.nextToken()); // 신청한 사람 수
            int maximum = Integer.parseInt(st.nextToken()); // 최대 인원
            Integer[] point = new Integer[people]; // 과목에 신청한 사람들의 점수를 담는 배열

            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < people; j++) {
                point[j] = Integer.parseInt(st.nextToken());
            }

            // 내림차순 정렬
            Arrays.sort(point, Collections.reverseOrder());

            if (maximum > people) {
                minimum[i] = 1;
            } else {
                minimum[i] = point[maximum-1]; // 그 과목에 필요한 최소 마일리지
            }
        }

        // 최소 마일리지 배열 오름차순 정렬
        Arrays.sort(minimum);

        // 최소 마일리지 배열에서 과목 수 구하기
        for (int i = 0; i < minimum.length; i++) {
            if (m >= minimum[i]) {
                m -= minimum[i];
                ans++;
            }
        }

        System.out.println(ans);
    }
}

- 내림차순 정렬

Arrays.sort(point, Collections.reversOrder());

 

1. 수강신청 인원이 최대 인원 수 보다 작으면 그냥 1점 사용

2. 그렇지 않을때는 점수들을 내림차순으로 정렬한 뒤 최대 인원수-1 의 인덱스값을 뽑아내면 그게 최소로 필요한 마일리지

3. 이런식으로 그 과목에 필요한 마일리지 최솟값을 배열에 담고 다시 오름차순 정렬

4. 내 마일리지 점수에서 배열에 든 마일리지 값을 빼가면서 과목수 ++

 

 


https://www.acmicpc.net/problem/12018

'PS > boj' 카테고리의 다른 글

boj)18352 - 특정 거리의 도시 찾기  (0) 2020.09.02
boj)1459 - 걷기  (0) 2020.08.31
boj)2012 - 등수 매기기  (0) 2020.08.31
boj)1911 - 흙길 보수하기  (0) 2020.08.31
boj)8958  (0) 2020.08.29