[Baekjoon] 11256_사탕

Silver V

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

---

< 사탕 >

 

문제 풀이 

 

최소한의 상자 개수를 사용하기 위해서는 상자가 큰 순서대로 정렬 후 사탕을 담을 수 있는 만큼 담으면 된다.

 

 my solution (Java)

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

public class _11256_ { // 사탕

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

		int t = Integer.parseInt(bf.readLine());

		PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());

		for (int i = 0; i < t; i++) {
			st = new StringTokenizer(bf.readLine());

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

			int result = 0;

			for (int k = 0; k < n; k++) {
				st = new StringTokenizer(bf.readLine());

				int r = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());

				queue.add(r * b);
			}

			while (j > 0) {
				result += 1;
				j -= queue.poll();
			}

			bw.write(result + "\n");
			queue.clear();
		}
		bw.flush();
	}
}

 

Main

변수)
t : 테스트 케이스 개수
queue : 우선순위 큐(내림차순)
j : 사탕의 개수
n : 상자의 개수
result : 최소한의 상자 개수
r : 상자의 세로 길이
b : 상자의 가로길이

 

- 테스트 케이스 개수(t) 입력

- 테스트 케이스 수(t) 만큼 반복해서 입력

: 사탕의 개수(j), 상자의 개수(n) 입력

: 상자의 개수(n) 만큼 반복해서 상자의 세로 길이, 가로길이 입력 후 [ 세로 길이 x 가로길이 ]를 우선순위 큐에 저장

: 사탕을 다 담을 때까지 우선순위 큐에서 상자를 꺼내 담기

: 최소한의 상자 개수(result) 출력

---

---