[백준 7774] 콘센트 - JAVA

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

 

그리디, 정렬

 

접근(그리디)

- 두 번째 멀티탭은, 최대한 많이 연결한다.

- 첫 번째 멀티탭은, 두 번째 멀티탭을 최대한 많이 연결하게 하는 선에서 최소로 사용해야 한다.

- ai, bi >= 1이므로, A플러그 - 첫 번째 - 두 번째 꼴을 만들 수만 있다면 최적이다

(손해는 안보고, 이득은 볼 수 있으므로 무조건 연결해도 된다.)

 

풀이 

B플러그가 가장 많은 두 번째 멀티탭을 연결하고 시작한다.

0개라 연결할 수 없거나, 연결하면 손해인 경우는  N == 0 || M == 0으로 이미 걸렀기 때문이다.

 

이후, B플러그가 다 사용될 때 까지 A플러그가 최대인 첫 번째 멀티탭을 꼽는다.

B플러그를 다 사용했다면, 연결된 첫번 째 멀티탭의 A 플러그에 두 번째 멀티탭을 꼽는다. 

 

(ai, bi >= 1이므로, 두 번째 멀티탭이 남아있는 이상 첫 번째 멀티탭을 꼽지 못하는 경우는 없다. 고려하지 않아도 된다.)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());

    st = new StringTokenizer(br.readLine());
    int[] a = new int[N];
    for (int i = 0; i < N; i++) {
      a[i] = Integer.parseInt(st.nextToken());
    }
    Arrays.sort(a);

    st = new StringTokenizer(br.readLine());
    int[] b = new int[M];
    for (int i = 0; i < M; i++) {
      b[i] = Integer.parseInt(st.nextToken());
    }
    Arrays.sort(b);

    if (N == 0 || M == 0) {
      System.out.println(1);
      return;
    }

    int plug = 0;

    int ai = N - 1;
    int bi = M - 1;

    while (bi >= 0 && ai >= 0) {

      if (a[ai] > 0) {
        plug += b[bi--];
        a[ai]--;
      } 

      else {
        plug--;
        ai--;
      }
    }

    if (ai == -1) {
      plug++;
    }
    System.out.println(plug);
  }
}