[Baekjoon] 33094_Diet Plan

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

---

< Diet Plan >

 

문제 풀이 

 

우선순위 큐에 우유를 저장하며 총 우유의 양이 m보다 커지면 그중에서 가장 많은 양의 우유를 비스킷으로 대체한다.

 

my solution (Java)

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

public class _33094_ { // Diet Plan

	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 m = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		int arr[] = new int[n];

		st = new StringTokenizer(bf.readLine());
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
		int cnt = 0, sum = 0;
		while (cnt < n) {
			queue.add(arr[cnt]);
			sum += arr[cnt];

			if (sum > m) {
				if (k == 0) {
					break;
				}
				k -= 1;
				sum -= queue.poll();
			}
			cnt += 1;
		}
		System.out.println(cnt);
	}
}

변수)
n, m, k : 일, 마셔야 하는 우유, 비스킷 수
arr : 각 날짜마다 마셔야 하는 우유 양
queue : 우선순위 큐
cnt, sum : 식단을 유지할 수 있는 날, 현재 마신 우유 양 

 

일, 마셔야 하는 우유 양, 비스킷 수를 입력받는다. n만큼 각 날짜마다 마셔야 하는 우유의 양을 입력받아 arr에 저장한다. 우선순위 큐에 하나씩 저장하며 현재까지 총합이 m보다 크다면 가장 많은 우유 양을 비스킷으로 대체한다. 만약 비스킷이 없다면 종료한다. 최종 cnt를 출력한다. 

---

---