[백준] 23254 기말고사형 인간이야 - Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

/*
나는 기말고사형 인간이야
https://www.acmicpc.net/problem/23254
 */

public class Main {

    static int n; // 시간
    static int m; // 과목
    static int[] basic; // 기본 점수
    static PriorityQueue<growth> growths; // 성장률

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()) * 24;
        m = Integer.parseInt(st.nextToken());

        basic = new int[m];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            basic[i] = Integer.parseInt(st.nextToken());
        }

        growths = new PriorityQueue<>();
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            int number = Integer.parseInt(st.nextToken());
            growths.add(new growth(i, number));
        }

        while(n > 0 && !growths.isEmpty()) {
            growth p = growths.poll();
            int time = ((100 - basic[p.id]) / p.number);
            int realTime = Math.min(n, time);

            n -= realTime;
            basic[p.id] += p.number * realTime;

            if(basic[p.id] != 100) {
                growths.add(new growth(p.id, 100 - basic[p.id]));
            }

        }

        int answer = 0;
        for (int i = 0; i < m; i++) {
            answer += basic[i];
        }

        System.out.println(answer);

    }


    // 성장률 내림차순
    public static class growth implements Comparable<growth> {
        int id;
        int number;

        growth(int id, int number) {
            this.id = id;
            this.number = number;
        }

        public int compareTo(growth g) {
            return g.number - this.number;
        }

    }

}

 

 

 

문제 출저

 

 

 

문제 풀이

주어진 시간에 공부할 과목을 선택하고 투자하여 최대한 많은 점수를 얻어야 합니다. 한 과목당 점수는 100점을 넘길 수 없습니다. 

 

우선순위큐와 그리디로 문제를 풀었습니다. 

우선순위큐에는 시간 당 점수 상승 폭이 높은 순으로 나오도록 뽑습니다. 

과목당 시간을 투자했을 때 2가지 경우의 수가 있습니다. 

 

1. 투자의 결과가 100으로 딱 맞을 경우

그대로 과목을 저장합니다.

 

2. 투자의 결과가 100으로 딱 안 맞을 경우

100 - [현재 점수]를 성장률로 다시 우선순위큐에 집어넣습니다. 

 

 

 

소스 코드