[Baekjoon] 13984_Contest Score

문제(출처: https://www.acmicpc.net/problem/13984)

---

< Contest Score >

 

문제 풀이 

 

우선순위 큐를 사용하여 문제 풀이 시간이 짧은 문제를 선택해서 푼다. 

페널티 시간 = 모든 문제의 제출 시간을 합한 값

 

my solution (Java)

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

public class _13984_ { // Contest Score

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		PriorityQueue<Integer> queue = new PriorityQueue<>();
		long result = 0, time = 0;

		for (int i = 0; i < n; i++) {
			int t = Integer.parseInt(bf.readLine());

			queue.add(t);
			if (queue.size() == k) {
				time += queue.poll();

				result += time;
			}
		}
		while (!queue.isEmpty()) {
			time += queue.poll();
			result += time;
		}
		System.out.println(result);
	}
}

변수)
n, k : 문제 수, 기억할 수 있는 문제 수
queue : 우선순위 큐
result, time : 페널티 시간, 문제 제출 시간
t : 해결하는 데 걸리는 시간 

 

문제 수와 한 번에 기억할 수 있는 문제 수를 입력받는다. 문제 수만큼 해결하는 데 걸리는 시간을 입력받으며 queue에 저장한다. 이때, queue의 size가 k와 같다면 queue에서 poll 하여 문제 제출 시간을 구한 후 페널티 시간에 더한다. 최종 queue가 빌 때까지 poll 하여 문제 제출 시간을 페널티 시간에 더한다.

 

최종 result를 출력한다.

---

---