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;
}
}
}
'OJ' 카테고리의 다른 글
[BOJ] 1240 노드사이의 거리 (JAVA) (0) | 2022.12.25 |
---|---|
[BOJ] 16441 아기돼지와 늑대 (JAVA) (0) | 2022.12.23 |
[BOJ] 17834 사자와 토끼 (JAVA) (0) | 2022.12.20 |
[BOJ] 1600 말이 되고픈 원숭이 (JAVA) (0) | 2022.12.13 |
[BOJ] 1743 음식물 피하기 (JAVA) (3) | 2022.12.11 |