백준 12915 - 대회 개최(자바 - 그리디)

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

12915번: 대회 개최

 

* 문제 요약

현종이는 프로그래밍 대회를 개최하는 것을 매우 좋아한다. 현종이는 프로그래밍 대회를 위해서 문제를 매우 많이 만들어놓았고, 이제 이 문제를 이용해서 프로그래밍 대회를 몇 번 개최할 수 있는지 알아보려고 한다.

현종이가 개최하는 프로그래밍 대회는 문제 3개로 이루어져 있고, 쉬운 문제, 중간 문제, 어려운 문제로 구성되어 있다.

대회를 개최하기 위해서는 문제 3개가 모두 있어야 한다.

현종이는 지금까지 만든 문제를 총 5가지 난이도로 분류했으며, 난이도는 다음과 같다.

- E개의 문제는 쉬운 문제로 사용할 수 있다.

- EM개의 문제는 쉬운 문제나 중간 문제로 사용할 수 있다.

- M개의 문제는 중간 문제로 사용할 수 있다.

- MH개의 문제는 중간 문제나 어려운 문제로 사용할 수 있다.

- H개의 문제는 어려운 문제로 사용할 수 있다.

 

모든 문제는 한 대회에서만 사용할 수 있으며, 한 가지 난이도로만 사용할 수 있다.

현종이가 대회를 최대 몇 번 열 수 있는지 구하는 프로그램을 작성하시오.

 

* 입력

첫째 줄에 E, EM, M, MH, H 가 주어진다. (0 <= E, EM, M, MH, H <= 100,000)

 

* 출력

첫째 줄에 현종이가 프로그래밍 대회를 최대 몇 번 열 수 있는지 출력한다.

 

* 예시

 

* 해결 과정

입력받은 e, em, m, mh, h 각 난이도별 문제 중에서 대회마다 쉬움(e, em), 중간(em, m, mh), 어려움(mh, h) 난이도의 문제 각 1개씩 낸다고 했을 때 대회를 최대 몇번 열 수 있는지 알아내야 한다.

처음엔 이분탐색 태그에서 찾은 문제이기에 이분탐색을 활용하여 문제를 풀어내려고 했으나, 로직 내부에서 여러모로 따져야 할 부분이 너무 많아져 그냥 그리디 방식으로 문제를 풀기로 했다.

다음과 같이 반복문을 진행해준다.

1. 쉬움 -> 중간 -> 어려움 순으로 문제를 하나씩 추출하는 방식으로 진행한다.

2. 각 난이도별로 문제를 출제할 때 우선 e, m, h 급 난이도(단일로만 문제를 출제할 수 있는 난이도) 의 갯수를 먼저 확인하고, 만약 해당 난이도 문제의 갯수가 0일 경우 em 또는 mh급 문제를 출제할 수 있는지 검사한다.

3. 현재 e급 난이도의 문제 갯수가 0보다 클 경우 e급 난이도에서 쉬움 난이도에 해당하는 문제를 출제하고, 그렇지 않을 경우 em급 난이도에서 문제를 출제한다. em급 난이도조차 0일 경우 반복문을 강제 종료시킨다.

4. 현재 m급 난이도의 문제 갯수가 0보다 클 경우 m급 난이도에서 중간급 난이도에 해당하는 문제를 출제하고, 그렇지 않을 경우 다음과 같이 조건에 따라 처리한다.

  - em급 난이도의 문제 갯수가 0보다 크면서 mh급 난이도의 문제 갯수보다 많을 경우 em급 난이도의 문제를 출제한다.

  - mh급 난이도의 문제 갯수가 0보다 크면서 em급 난이도의 문제 갯수보다 많을 경우 mh급 난이도의 문제를 출제한다.

  - em급 난이도와 mh급 난이도의 문제 갯수가 같고, em급 난이도의 문제 갯수가 0보다 클 경우 em급 난이도의 문제를 출제한다.

(em급 난이도의 문제를 먼저 배정하는 이유 : 쉬움에 이미 한 문제가 출제되어 있고 중간급 문제를 출제해야 하는데 m급 난이도는 이미 0이라서 em, mh 중 하나를 출제해야 하는 상황이라고 해보자.

이때 중간급 문제에 mh급 난이도의 문제를 먼저 출제할 경우 뒤에 나오는 어려움 문제를 출제하는데 문제가 발생하게 될 수 있다. 그렇게 되면 자연스럽게 대회를 열 수 있는 최대 횟수에 가장 근접한 값에 도달할 수 없게된다. 그러므로 mh급 난이도 대신, 앞에서 이미 출제된 em급 난이도를 출제하는 것이 현재 상황에서 성공적으로 대회를 개최시키는데 최적의 선택이 될 수 있다.)

5. 현재 h급 난이도의 문제 갯수가 0보다 클 경우 h급 난이도에서 어려움 난이도에 해당하는 문제를 출제하고, 그렇지 않을 경우 mh급 난이도에서 문제를 출제한다. mh급 난이도조차 0일 경우 반복문을 강제 종료시킨다.

6. 위의 모든 조건을 통과한 경우 count 변수 값을 1증가시킨다.

7. 반복문이 종료되고 나면 count 값을 반환해주고 이를 출력시킨다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

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

    static int[] contestArray = null;
    private void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

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

    private int contestOpen() {

        // 그리디 방식으로 E, M, H 난이도로 mid 만큼 만들 수 있는지 확인
        int count = 0;
        while(true){

            // easy
            if(contestArray[0] > 0){
                contestArray[0]--;
            } else {
                if(contestArray[1] > 0){
                    contestArray[1]--;
                } else{
                    break;
                }
            }
            // medieum
            if(contestArray[2] > 0){
                contestArray[2]--;
            } else{
                if(contestArray[1] > 0 && contestArray[1] > contestArray[3]){
                    contestArray[1]--;
                } else if(contestArray[3] > 0 && contestArray[3] > contestArray[1]){
                    contestArray[3]--;
                } else if(contestArray[1] == contestArray[3] && contestArray[1] > 0){
                    contestArray[1]--;
                } else {
                    break;
                }
            }
            // hard
            if(contestArray[4] > 0){
                contestArray[4]--;
            } else {
                if(contestArray[3] > 0){
                    contestArray[3]--;
                } else {
                    break;
                }
            }
            
            count++;
        }

        return count;
    }
}

 

현재 상황에서 최적의 해답을 선택한다. -> 쉬움 -> 중간 -> 어려움 순으로 문제를 출제하는데 있어 중간 문제를 출제할 때 후에 나올 어려움에 해당하는 문제를 출제하면서 발생할 수 있는 문제를 방지하기 위해 mh급 난이도보다 em급 난이도의 문제를 먼저 출제하는등, 각 상황에서 대회를 성공적으로 개회하기 위해 최적의 해답을 선택하였다.

선택된 해답이 조건을 만족하는지 검사한다. -> 쉬움, 중간, 어려움 각 난이도의 문제들을 각각 1개씩 성공적으로 출제한 경우 대회 개최횟수(count) 를 1 늘리는 로직을 단 하나의 난이도에서라도 문제를 출제하지 못하게 될 때까지 반복해줌으로서 대회를 개최할 수 있는 최대 횟수를 구했다.

 

위의 과정을 통해 문제를 해결하였으므로 그리디 알고리즘 문제에 해당된다.