BOJ 백준온라인져지 15708 미네크래프트 풀이

1. 1 ~ N 까지에서 가장 Ki가 높은것들을 차례대로 될때까지 뺀다.

	import java.util.*;
	import java.io.*;
	/**
	* https://www.acmicpc.net/problem/15708
	* BOJ 백준온라인져지 15708 미네크래프트 풀이
	*/
	public class Main {
	private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	public static void main(String args[]) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	String str1[] = br.readLine().split(" ");
	int N = Integer.parseInt(str1[0]);
	long T = Long.parseLong(str1[1]);
	long P = Long.parseLong(str1[2]);
	String str2[] = br.readLine().split(" ");
	int sum = 0;
	PriorityQueue<Integer> pq = new PriorityQueue<>();
	int max = 0;
	for (int i = 0; i < N; i++) {
	int K = Integer.parseInt(str2[i]);
	sum += K;
	pq.offer(-K);
	while (sum > T - i * P) {
	if (pq.size() == 0) break;
	sum += pq.poll();
	}
	max = Math.max(max, pq.size());
	}
	bw.write(String.valueOf(max));
	bw.flush();
	}
	}

view raw Main.java hosted with ❤ by GitHub

문제

미네크래프트에 있는 디디는 집을 짓기 위해 돌을 채취하려고 한다. N개의 바위들이 일렬로 놓여져 있고, 디디는 현재 첫번째 바위에 위치해 있다. 각 바위 i는 서로 같거나 다른 강도를 가지고 있어서, 바위에서 돌을 채취하기 위해 해야 하는 곡괭이질의 수 Ki 또한 서로 같거나 다르다. 디디는 돌을 채취하기 위해 다음과 같은 행동을 할 수 있다.

1. 시간 1을 소비하여, 디디 앞에 있는 바위에 곡괭이질을 1번 한다.
2. 시간 P를 소비하여, 이웃한 바위로 이동한다.

디디에게 T만큼의 시간이 주어졌을 때, 채취할 수 있는 돌의 최대 개수를 출력하는 프로그램을 작성하라.

입력

첫째 줄에 정수 N(1 ≤ N ≤ 105), T(1 ≤ T ≤ 109), P(1 ≤ P ≤ 105)가 공백으로 구분되어 주어진다.

둘째 줄에 바위 i(i = 1, 2, ..., N)를 채취하기 위해 필요한 곡괭이질의 수 Ki(1 ≤ Ki ≤ 105)가 공백으로 구분되어 주어진다.

출력

문제의 정답을 출력하라.

예제 입력 1 

6 17 1
3 5 2 6 9 1

예제 출력 1 

4

힌트

출처

Contest > 네블컵 > 제 1회 네블컵 B번