백준 3213 - 피자 (자바 - 그리디)

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

3213번: 피자

 

* 문제 요약

상근이는 생일을 기념해 친구들과 피자를 먹으러갔다.

친구들은 매우 어려서 피자 한 판을 먹을 수 없다. 하지만 각 친구들은 자신이 먹을 수 있는 피자의 양을 알고 있다.

친구들이 먹을 수 있는 피자의 양은 항상 1/4, 1/2, 3/4 중 하나이다.

피자 최소 몇 판을 시키면 친구들이 모두 피자를 자신이 먹을 수 있는 양만큼 먹을 수 있는지 구하는 프로그램을 작성하시오.

상근이는 피자를 먹지 않으며, 모든 친구들이 정확히 한 조각씩 피자를 가져야 한다.

 

* 입력

첫째 줄에 친구의 수 N 이 주어진다. (1 <= N <= 10,000) 

다음 N 개의 줄에는 각 친구가 먹을 수 있는 피자의 양이 주어진다. 이 값은 항상 분수이며, 1/4, 1/2, 3/4 중 하나이다.

 

* 출력

피자를 최소 몇 판 시키면 모든 친구들이 자신이 먹을 수 있는 양만큼 먹는지 출력한다.

 

* 예시

 

* 해결 과정

매 반복마다 먹을 수 있는 만큼의 피자를 먹고 난 후 남은 피자들은 모두 버려야 하는지 다시 쓸 수 있는지 감을 잘 못잡아서 많이 애먹었던 문제다.

 

피자 한 판을 100 이라고 설정하고 친구들이 먹을 수 있는 양 1/4, 1/2, 3/4 를 각각 25, 50, 75 로 설정해서 피자 배열에 저장했다.

이 배열을 내림차순 정렬해준 다음 반복문으로 순차탐색을 하면서 현재 탐색중인 친구가 주문이 나와있는 피자 한판을 기준으로 얼마나 먹을 수 있는지 판별한다.

 

친구가 먹을 수 있는 크기가 현재 나와있는 피자 크기보다 작다면 먹을 수 있는 것으로 판단하고, 현재 나와있는 피자의 크기를 친구가 먹을 수 있는 크기만큼 줄인다.

만약 친구가 먹을 수 있는 크기 보다 현재 나와있는 피자 크기가 작은 경우, 현재 나와있는 피자는 여분의 피자로 남겨둔 다음, 앞전에 나온 여분의 피자 중에서 현재 친구가 먹을 수 있는 크기의 피자가 있는지 찾아본다.

만약 여분의 피자 중 현재 친구가 먹을 수 있는 크기의 피자가 있는 경우 해당 피자를 여분의 피자 리스트에서 삭제해준다.

(더 정확하게 하자면 크기를 비교해서 여분의 피자 크기가 친구가 먹을 수 있는 피자의 크기보다 더 큰 경우 리스트에서 삭제하지 않고 크기만 줄여서 다시 리스트에 넣어줘야 하는데, 일단 리스트에서 삭제하기만 해도 통과를 받기에는 문제가 없는 것이 확인되었다.)

 

만약 여분의 피자 중에서도 현재 친구가 먹을 수 있는 크기의 피자가 없는 경우 새로 피자를 한 판 시켜서 (피자 값을 100 으로 초기화) 현재 친구에게 피자를 먹여주고, 주문 시킨 피자의 갯수를 늘려준다.

 

위의 과정을 모든 친구들이 피자를 먹을 수 있을 때까지 반복한다.

 

* 코드

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

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());
        Integer [] pizza = new Integer[count];
        int result = 100;
        int pizzaCount = 1;
        for(int i = 0; i < count; i++){
            String str = br.readLine();

            if(str.equals("1/4")){
                pizza[i] = 25;
            }
            else if(str.equals("1/2")){
                pizza[i] = 50;
            }
            else if(str.equals("3/4")){
                pizza[i] = 75;
            }
        }

        Arrays.sort(pizza, Collections.reverseOrder());
        List<Integer> spare = new ArrayList<>();
        for(int i = 0; i < count; i++){
            if(result >= pizza[i]){
                result -= pizza[i];
            }
            else{
                spare.add(result);
               
                int index = i;
                if(spare.stream().filter(x -> x >= pizza[index]).count() > 0){
                    for(int j = 0; j < spare.size(); j++){
                        if(spare.get(j) >= pizza[index]){
                            spare.remove(j);
                            break;
                        }
                    }
                }
                else{
                    pizzaCount++;
                    result = 100 - pizza[i];
                }
            }
        }

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

 

피자 주문량을 최소화 하기 위해 먹을 수 있는 피자의 크기를 기준으로 배열을 내림차순 정렬 한 점, 

그리고 주문 시킨 후 남아있는 피자 중 먹을 수 있는 피자가 있다면 추가 주문을 하지 않고 여분의 피자를 내준점에서 매 단계마다 전체를 기준으로 최적에 가까운 해를 찾기 위해 로직을 최적화 했으므로 그리디 알고리즘 문제에 해당된다.