백준 11256 - 사탕 (자바 - 그리디)

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

11256번: 사탕

 

* 문제 요약

날마다 j 개의 사탕을 상자에 포장해야 한다.

크기가 다른 N 개의 상자를 가지고 있다. 편리를 위해 상자를 최소한으로 쓰려고 한다.

(박스를 다 채울 필요는 없다. 일부분만 채워도 된다.)

공장에서 나오는 사탕의 개수와 각 상자의 크기를 입력받고, 상자를 최소한으로 쓸 때 사용되는 상자의 개수를 출력하는 프로그램을 작성하라.

사탕들을 포장할 공간이 충분하다는 것이 보장된다.

 

* 입력

첫번째 줄에는 테스트케이스의 개수 T (1 <= T <= 10) 가 주어진다.

테스트 케이스의 첫번째 줄에는 사탕의 개수 j 와 상자의 개수 N 이 주어진다. (1 <= j, N <= 1000)

다음 N 개의 줄에는 각각 줄마다 i 번째 상자의 세로 길이 R, 가로 길이 C 가 주어진다.

상자의 크기는 다른 상자의 크기와 똑같을 수도 있다.

상자에는 R * C 보다 더 많은 사탕을 포장할 수 없다. (1 <= R <= 10000)

 

* 출력

각각의 줄마다 테스트 케이스에서 최소한의 상자 개수를 출력해야 한다.

 

* 예시

 

* 해결 과정

- 입력받은 r, c 값을 통해 상자의 넓이를 구한 다음, 해당 값을 boxArray 배열에 저장해둔다.

- 박스를 최소한으로 사용하려면 넓이가 큰 상자들부터 순서대로 사용해야 하므로 boxArray 를 내림차순 으로 정렬한다.

- 상자의 갯수를 기준으로 반복문을 수행하되, 매 반복마다 사탕의 갯수에서 현재 탐색중인 상자의 넓이만큼을 빼고, 사용한 상자의 갯수를 표현하는 변수 result 에 1 을 더해준다.

- 뺄셈을 수행한 이후 사탕의 갯수가 0 보다 작거나 같아지면 반복문을 종료하고 사용된 상자의 갯수 result 를 출력해준다.

 

* 코드

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

public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int count = Integer.parseInt(br.readLine());

        for (int i = 0; i < count; i++) {
            String[] input = br.readLine().split(" ");
            int candyCount = Integer.parseInt(input[0]);
            int boxCount = Integer.parseInt(input[1]);
            Integer[] boxArray = new Integer[boxCount];

            for (int j = 0; j < boxCount; j++) {
                input = br.readLine().split(" ");
                int r = Integer.parseInt(input[0]);
                int c = Integer.parseInt(input[1]);

                boxArray[j] = r * c;
            }
            Arrays.sort(boxArray, Collections.reverseOrder());

            int result = 0;
            for (int j = 0; j < boxArray.length; j++) {
                candyCount -= boxArray[j];
                result++;

                if (candyCount <= 0)
                    break;
            }

            bw.write(result + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

 

최적의 상황을 만들어주기 위해 상자의 넓이를 내림차순으로 정렬해준 뒤, 현재 단계에서 상자의 넓이만큼 사탕의 갯수를 감소시키는 방식으로 문제를 풀었다.

매 단계마다 최적인 로직을 수행한 결과가 그 다음 단계에 영향을 미치지 않으므로 그리디 알고리즘 문제라고 볼 수 있다.