11256번. 사탕

 

아이디어

상자를 최소한으로 쓰기 위해서는 용량이 큰 상자부터 꽉꽉 채워담아야 한다. 만약 사용한 상자를 모두 다 채워야 한다고 하면 이야기가 다르겠지만 문제에서 상자를 다 채우지 않아도 된다고 했으므로 그리디한 방식으로 문제를 해결하면 된다.

 

 

풀이코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        for (int t = 0; t < T; t++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int J = Integer.parseInt(st.nextToken()); // 사탕의 개수
            int N = Integer.parseInt(st.nextToken()); // 상자의 개수

            int[] boxes = new int[N];
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(br.readLine());

                int R = Integer.parseInt(st.nextToken());
                int C = Integer.parseInt(st.nextToken());

                boxes[i] = R * C;
            }

            Arrays.sort(boxes);

            int idx = N - 1;
            while (J > 0) {
                J -= boxes[idx--];
            }

            sb.append(N - 1 - idx).append("\n");
        }

        System.out.println(sb);
    }
}