본문 바로가기

OJ

[BOJ] 23254 나는 기말고사형 인간이야 (JAVA)

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

 

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

192시간 동안 1번 과목을 35시간, 2번 과목을 43시간, 3번 과목을 30시간, 4번 과목을 17시간, 5번 과목을 37시간, 6번 과목을 30시간동안 공부하면 1, 2, 3, 4, 6번 과목은 100점, 5번 과목은 77점, 7번 과목은

www.acmicpc.net

그리디 문제입니다.

우선순위 큐를 이용하여 해결했습니다.

Subject 객체의 points가 현재 점수이고, pph는 시간당 얻을 수 있는 점수입니다.

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N, M, result;
	static int[] a, b;
	
	public static void main(String[] args) throws Exception {
		
		st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken()) * 24;
		M = Integer.parseInt(st.nextToken());
		a = new int[M];
		b = new int[M];
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < M; i++) {
			a[i] = Integer.parseInt(st.nextToken());
		}
		st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < M; i++) {
			b[i] = Integer.parseInt(st.nextToken());
		} // end of input
		
		PriorityQueue<Subject> pq = new PriorityQueue<>();
		for (int i = 0; i < M; i++) {
			pq.offer(new Subject(a[i], b[i]));
		}
		
		while(N != 0) {
			
			Subject s = pq.poll();
			
			// 시간이 남았는데 모두 100점이면 탈출
			if(s.pph == 0) {
				result += s.points;
				break;
			}
			
			int hours = (100 - s.points) / s.pph;
			
			// 공부할 시간이 충분하면
			if(hours <= N) N -= hours;
			// 충분하지 않으면
			else {
				hours = N;
				N = 0;
			}
			// 공부한 뒤 새 점수
			int newPoints = s.points + s.pph * hours;
			
			pq.offer(new Subject(newPoints, 100 - newPoints < s.pph ? 100 - newPoints : s.pph));
			
		}
		
		// 계산이 끝났으니 결과를 모두 result에 담음
		while(!pq.isEmpty()) {
			result += pq.poll().points;
		}
		
		System.out.println(result);
		
	}
	
	static class Subject implements Comparable<Subject> {
		
		int points, pph;

		public Subject(int points, int pph) {
			this.points = points;
			this.pph = pph;
		}

		@Override
		public int compareTo(Subject o) {
			return o.pph - this.pph;
		}
		
	}
	
}