백준 12981 - 공 포장하기 (자바 - 그리디)

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

12981번: 공 포장하기

 

* 문제 요약

빨간 공 R 개, 초록 공 G 개, 파란 공 B 개를 가지고 있다.

오늘은 이 공을 박스로 포장하려고 한다. 박스에는 공이 1개, 2개, 또는 3개 들어갈 수 있다.

박스에 들어가는 공의 색은 모두 다르거나, 모두 같아야 한다.

필요한 박스 갯수의 최솟값을 구하는 프로그램을 작성하시오.

 

* 입력

첫째 줄에 R, G, B 가 주어진다. (1 <= R, G, B <= 100)

 

* 출력

첫째 줄에 필요한 박스 갯수의 최솟값을 출력한다.

 

* 예시

 

* 해결 과정

각 상자안에 공을 1개, 2개, 또는 3개까지 들어갈 수 있는데, 사용하는 박스를 최소화 시키려면 공이 3개씩 들어가는 박스의 숫자가 최대한 많아져야 한다.

공을 넣을 수 있는 조합은 서로 색깔이 다른 공 n 개를 넣거나, 또는 색깔이 같은 n 개의 공을 넣거나이다.

여기서는 첫번째로 색깔이 같은 공들부터 먼저 불가능해질 때까지 3개씩 상자에 넣는다.

 

각 색깔별로 3개씩 최대한 상자에 넣고 난 뒤 남은 공들에 대해서는 아래와 같은 2가지 경우에 따라 사용되는 상자의 갯수를 따로따로 구한다.

- 3개씩 포장하고 남은 공들을 모두 1개씩 서로 다른 색깔의 공으로 조합하여 상자에 넣는 경우

- 3개씩 포장하고 남은 공들 중에서 갯수가 2개인 공들이 있으면, 그 공들을 먼저 따로 상자에 한번에 집어넣은 다음, 또 다시 남은 공들에 대해 1개씩 서로 다른 색깔의 공으로 조합하여 상자에 넣는 경우

 

위의 2가지 경우 중 더 작은 값과 처음에 같은 색깔의 공 3개씩 상자에 넣은 횟수를 더하여 정답을 출력해준다.

 

* 코드

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;
import java.util.LinkedList;
import java.util.Queue;

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

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

        String[] input = br.readLine().split(" ");
        Integer[] ballArray = new Integer[input.length];
        for (int i = 0; i < input.length; i++) {
            ballArray[i] = Integer.parseInt(input[i]);
        }

        for (int i = 0; i < ballArray.length; i++) {
            if (ballArray[i] >= 3) {
                result += ballArray[i] / 3;
                ballArray[i] = ballArray[i] % 3;
            }
        }

        Arrays.sort(ballArray);
        Integer[] temp = ballArray.clone();

        int oneColor = 0;
        Queue<Integer> boxQueue = new LinkedList<>();
        while (true) {
            for (int i = 0; i < temp.length; i++) {
                if (temp[i] >= 1) {
                    boxQueue.offer(ballArray[i]);
                    temp[i] -= 1;
                }
            }

            if (boxQueue.size() >= 1 && boxQueue.size() <= 3) {
                boxQueue.clear();
                oneColor++;
            } else
                break;
        }

        Arrays.sort(ballArray, Collections.reverseOrder());
        temp = ballArray.clone();
        int twoColor = 0;
        for (int i = 0; i < temp.length; i++) {
            if (temp[i] == 2) {
                twoColor++;
            } else if (temp[i] == 1) {
                boxQueue.offer(temp[i]);
            }
        }
        if (boxQueue.size() >= 1 && boxQueue.size() <= 3) {
            twoColor++;
        }
        result += Math.min(oneColor, twoColor);

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

 

- 같은 색깔의 공 3개를 상자에 넣는 경우

- 남은 공들 중에서 같은 색깔의 공이 2개 이상 있을 때, 그 공들부터 먼저 상자에 넣고 나서 나머지 공들을 서로 다른 색깔로 조합하여 상자에 넣는 경우

- 남은 공들 모두를 대상으로 서로 다른 색깔로 조합하여 상자에 넣는 경우

 

상자를 최소한으로 쓰는 경우를 찾기 위해 위와 같이 경우의 수를 최적화 하였고, 위의 3가지 경우의 결과를 구하는 과정에서 또한 현재 상황, 즉 현재 탐색중인 공의 색깔을 기준으로 남아있는 공의 갯수가 얼마나 되느냐에 따라 매 반복 단계마다 이후의 상황이 어떻게 되느냐와는 상관없이 최적의 로직을 수행시켰다.

그러므로 그리디 알고리즘 문제에 해당된다.