백준 23254 (나는 기말고사형 인간이야) - java

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

23254번: 나는 기말고사형 인간이야

 

문제

중간고사를 시원하게 망친 찬우는 오늘부터 1분도 쉬지 않고 기말고사 공부에 매진하기로 다짐했다.

기말고사는 정확히 24×N시간 이후에 시작되며, 쉬는 시간 없이 하루에 모든 과목의 시험을 보기 때문에 찬우는 24× N시간동안 공부할 수 있다. 기말고사를 보는 과목은 총 M개로, 시험 시간이 빠른 과목부터 각각 1$1$부터 �$M$까지의 번호가 매겨져 있다. 모든 과목의 최저점은 0점, 최고점은 100점이다.

찬우는 공부를 하나도 하지 않아도 i번 과목에서ai 점을 받을 수 있으며, i번 과목을 정확히 한 시간 공부할 때마다 그 과목의 성적을 bi점 올릴 수 있다. 하지만 i번 과목을 30분 공부한다고 bi점이 오르지는 않으며, 아무리 공부하더라도 한 과목에서 최고점인 100점이 넘는 점수를 받을 수는 없다. 

모든 과목의 점수의 합이 찬우의 최종 성적이 된다. 높은 성적을 받기 위한 최적의 전략으로 공부할 때, 찬우가 받을 수 있는 최종 성적의 최댓값을 출력하는 프로그램을 작성하시오.

 

유형 : 그리디 + 우선순위 큐

 

접근 방식

• 정렬 기준은 간단하다. 1시간 대비 가장 높은 점수가 오르는 과목을 많이 공부하면 된다. 즉 plus 점수를 기준으로 정렬하면 된다.
• 단 정말 주의할 점이 있는데 50점을 올릴 수 있는데 1시간 마다 3점이 오른다 가정하자
  • 결국 16시간 공부하면 48 점이 오르는데 여기서 1시간을 더 공부하면 2점이 오른다. (점수 최대치 : 100점)
  • 근데 뒤에 있는 과목은 1시간 당 1점이 오른다면....???
  • 그렇다. 앞의 과목을 1시간 더 공부하고 2점을 올리는게 효과적이다.
• 위 방식을 구현 하는 방법은 간단하다. 1시간 더 공부해서 올릴 수 있는 점수를 구하고 우선순위 큐에 추가 해주면 된다.
  • 위와 같이 할 경우 알아서 다음 큐 탐색 때 해당 시간과 점수를 고려할 수 있다.

전체 코드

import java.util.*;
import java.io.*;
public class Main {
    static int n = 0;
    static int m = 0;

    static int[] score;

    static int[] plus;

    static int total = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb =new StringBuilder();
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        score = new int[m];
        plus = new int[m];
        PriorityQueue<Node> pq = new PriorityQueue<>(
                (x,y) -> y.plus - x.plus
        );

        st = new StringTokenizer(bf.readLine(), " ");
        for(int i=0;i<m;i++){
            score[i] = Integer.parseInt(st.nextToken());
            total += score[i];
        }

        st = new StringTokenizer(bf.readLine(), " ");
        for(int i=0;i<m;i++){
            plus[i] = Integer.parseInt(st.nextToken());

            pq.add(new Node(100 - score[i],plus[i]));
        }

        int time = 24 * n;

        while(!pq.isEmpty()){
            Node cur = pq.poll();

            if(time >= (cur.rest / cur.plus)){
                time -= cur.rest / cur.plus;

                total += cur.plus * (cur.rest / cur.plus);

                if(cur.rest % cur.plus >= 1){
                    pq.add(new Node(cur.rest % cur.plus,cur.rest % cur.plus));
                }
            }else if(time > 0 && (cur.rest >= time * cur.plus)){
                total += time * cur.plus;
                time = 0;
            }
        }

        System.out.println(total);
        bf.close();
    }

}
class Node{
    int rest;
    int plus;

    Node(int rest,int plus){
        this.rest = rest;
        this.plus = plus;
    }
}