백준 7774 - 콘센트 (자바 - 그리디)

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

7774번: 콘센트

 

* 문제 요약

집에 많은 콘센트를 설치하려고 한다. 이때, 콘센트와 전기 플러그에 대한 표준은 두 개이다.

이 표준은 서로 호환성이 없기 때문에 표준 A 에 해당하는 플러그는 표준 A 에 해당하는 콘센트에만, B 에 해당하는 플러그는 B 에 해당하는 콘센트에만 꽂을 수 있다.

 

집에는 콘센트가 딱 한 개 있다. 이 콘센트는 표준 A 에 해당한다. 모든 컴퓨터는 표준 A 플러그를 사용한다.

따라서, 콘센트에 꽂을 수 있는 컴퓨터는 하나밖에 없다. 하지만 집에는 멀티탭 또한 존재한다.

멀티탭은 다음과 같이 두 종류가 있다.

- 첫 번째 멀티탭은 표준 A 플러그를 사용하고, 표준 B 콘센트를 여러개 가지고 있다.

- 두 번째 멀티탭은 표준 B 플러그를 사용하고, 표준 A 콘센트를 여러개 가지고 있다.

 

이 멀티탭은 매우 강력하기 때문에, 폭발하지 않고 모든 전류를 견뎌낼 수 있다. 따라서, 첫 번째 멀티탭을 콘센트에 꽂은 다음에, 그 콘센트에 두 번째 멀티탭을 꽂고... 이런식으로 꽂다보면 표준 A 에 해당하는 콘센트를 많이 얻을 수 있게 된다.

가지고 있는 각 멀티탭의 갯수가 주어졌을 때, 표준 A 콘센트를 최대 몇 개까지 만들 수 있는지 구하는 프로그램을 작성하시오.

 

* 입력

첫째 줄에는 가지고 있는 첫번째 멀티탭의 갯수 n, 두번째 멀티탭의 갯수 m 이 주어진다. (0 <= n, m <= 100,000)

둘째 줄에는 첫 번째 멀티탭에 있는 콘센트의 갯수 ai 가 공백으로 구분되어 주어진다. (1 <= ai <= 1,000)

셋째 줄에는 두 번째 멀티탭에 있는 콘센트의 갯수 bi 가 공백으로 구분되어 주어진다. (1 <= bi <= 1,000)

 

* 출력

최대 몇 개의 컴퓨터를 사용할 수 있는지 출력한다.

 

* 예시

 

* 해결 과정

A 콘센트 갯수와 B 콘센트 갯수를 입력으로 받아서 배열에 저장한 다음, 이 배열들을 내림차순 정렬하여 콘센트가 많은 멀티탭부터 우선적으로 사용하도록 하였다.

이후엔 초기 상태로 A 콘센트 갯수 1개, B 콘센트 갯수 0 개를 만들어 둔 다음 첫 번째 멀티탭, 두 번째 멀티탭 둘 중 어느 하나를 완전히 다 쓰게 되기 전까지 반복문을 진행했다.

 

반복문 내부에서는 현재 단계에서 A 콘센트 갯수가 0 보다 많을 경우 두 번째 멀티탭을 A 콘센트에 꽂았는데, 이때 결과적으로 A 콘센트 갯수를 최대화 시켜야 하므로 A 콘센트를 매 단계마다 한 개씩만 사용하게 만들었다.

그 다음엔 현재 B 콘센트의 갯수가 0 보다 많을 경우 아래의 2가지 조건이 만족되는 동안 이중 반복문을 수행하였다.

- 1. B 콘센트가 0 보다 많을 것

- 2. 두 번째 멀티탭이 모두 사용되지 않았을 것.

이중 반복문 내부에서는 현재 사용가능한 B 콘센트들에 두 번째 멀티탭들을 위의 2가지 조건 중 하나 이상이 만족되지 않을 때까지 연결해서 A 콘센트의 갯수를 최대한 늘려 주었다.

 

그렇게 이중 반복문이 끝나고 나면 현재 단계에서 구한 A 콘센트의 갯수와, 이전 단계에서 구했던 A 콘센트의 갯수를 비교하여 더 큰 쪽을 저장 시키는 방식으로 답을 구했다.

 

* 코드

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 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));

        String[] input = br.readLine().split(" ");
        int A = Integer.parseInt(input[0]);
        int B = Integer.parseInt(input[1]);

        Integer[] arrayA = new Integer[A];
        Integer[] arrayB = new Integer[B];

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

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

        Arrays.sort(arrayA, Collections.reverseOrder());
        Arrays.sort(arrayB, Collections.reverseOrder());

        int countA = 1;
        int countB = 0;

        int indexA = 0;
        int indexB = 0;

        int max = countA;
        while (indexA < arrayA.length && indexB < arrayB.length) {
            if (countA > 0) {
                countA--;
                countB += arrayA[indexA];
                indexA++;
            }

            if (countB > 0) {
                while (countB > 0 && indexB < arrayB.length) {
                    countB--;
                    countA += arrayB[indexB];
                    indexB++;
                }
            }

            max = Math.max(max, countA);
        }
        bw.write(max + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

A 콘센트의 갯수를 최대화 하기 위해 매 단계마다 현재 상황을 기준으로 A 콘센트의 사용은 최소화 하고, B 콘센트의 사용은 최대화 하여 A 콘센트의 갯수를 구했으므로 그리디 알고리즘 문제라고 할 수 있다.