[파이썬, 자바] BOJ_11256(사탕)

문제

 

https://www.acmicpc.net/problem/11256

11256번: 사탕

---

 

해설

 

상자의 세로 * 가로의 길이보다 더 많은 사탕을 포장할 수 없다는 건,

상자의 한 칸에 하나의 사탕만 넣을 수 있다는 것을 뜻한다.

한 칸에 사탕 하나

상자를 최소한으로 사용한다는 것은,

크기가 가장 큰 상자부터 사탕을 넣는다는 것을 뜻한다.

 

결국, 세로(r) * 가로(c)의 크기가 가장 큰 상자부터 사탕을 차감해나가면 된다는 것인데

이는 상자마다 세로(r) * 가로(c) 한 값을 리스트에 저장해 내림차순 정리를 해놓고 계산하면 된다.

 

 

---

코드

 

-파이썬

#백준 11256(사탕)
import sys
input = sys.stdin.readline

t = int(input())  #테스트 케이스 개수

for _ in range(t):
    candy, box = map(int, input().split())  #사탕, 상자
    box_list = []
    cnt = 0  #쓰인 상자 개수
    
    for i in range(box):
        r, c = map(int, input().split())  #세로, 가로
        box_list.insert(i, r * c)  #세로 * 가로 -> 리스트에 넣기

    box_list.sort(reverse= True)
    for j in range(box):
        candy = candy - box_list[j]
        cnt += 1
        if candy <= 0:
            break

    print(cnt)

 

-자바

//백준 11256(사탕)
import java.util.*;
import java.io.*;

public class Boj_11256 {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int t = Integer.parseInt(br.readLine());  //테스트 케이스 개수

		for(int i = 0; i < t; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			int candy = Integer.parseInt(st.nextToken());  //사탕 개수
			int box = Integer.parseInt(st.nextToken());  //상자 개수
			int cnt = 0;
			
			Integer[] box_list = new Integer[box];
					
			for(int j = 0; j < box; j++) {
				st = new StringTokenizer(br.readLine());
				
				int r = Integer.parseInt(st.nextToken());
				int c = Integer.parseInt(st.nextToken());
				box_list[j] = r * c;
				
			}
			Arrays.sort(box_list, Comparator.reverseOrder());  //내림차순 정렬
			
			for(int k = 0; k < box; k++) {
				candy = candy - box_list[k];
				cnt ++;
				
				if(candy <= 0) {
					break;
				}
			}
			
			System.out.println(cnt);
			
		}

	}

}