백준: 21761번 (초직사각형) [JAVA]

문제 링크

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

21761번: 초직사각형

풀이

전체적인 풀이 과정은 다음과 같다.

1. 각 A, B, C, D에 대한 좌표와, 각 카드 속 특정 좌표의 증가분을 저장할 long 타입 배열 생성 후 초기화
   
2. 각 좌표 별 증가분을 내림차순으로 정렬하는 우선순위 큐들을 생성 후, 주어지는 카드들 속 증가분을 저장
3. K 번에 걸쳐 아래 작업을 반복
   1) 각 좌표에 대한 우선 순위 큐에서 증가분을 꺼내 저장 (만약 없다면 0)
   2) 각 좌표별 증가분에 걸쳐 가장 부피가 많이 늘어나는 좌표와 증가분을 계산
   3) 해당 좌표에 대한 우선순위큐에서 해당 증가분을 꺼내 제거 후 좌표 최신화
   4) 해당 좌표, 증가분을 출력할 답에 추가
4. 결과 답을 출력

 문제에서는 기존 좌표들을 바탕으로 앞으로 각 좌표들에 대한 증가분 중 K 번을 골라 초직사각형의 부피가 최대가 되게 해야 한다. 이 때 중요한 점은 각 좌표의 중가분을 바탕으로 부피가 얼만큼 늘어났는지를 판단할 때 현 상황에서 초직사각형 좌표들의 값들이기 때문에, 각 카드들의 정보를 입력받는 과정에서 어떤 카드가 가장 효율이 좋은지를 판별하는 것은 불가능하다. 카드들을 입력받는 상태에서 1차적으로 확인 가능한 것은 단순히 해당 좌표의 증가분들 중 가장 큰 것이 어떤 것인지를 찾는 것뿐, 여러 좌표에 대한 증가분들 중에서 어느게 가장 나은 지는 그때 계산을 진행해야 한다.
 그렇기 때문에 우선 현재 각 좌표들을 저장하는 배열과 각 좌표들의 증가분을 저장하는 배열을 만들고 초기화한다. 그 다음엔 주어지는 일반적인 정보들을 저장하는데, 이 때 주어지는 카드들의 정보를 각 좌표에 해당하는 우선순위큐(내림차순 정렬)들에 나누어 저장한다. 그 다음에는 K 번에 걸쳐 카드를 뽑는 과정을 진행한다. 각 좌표에 해당하는 증가분을 우선순위 큐에서 하나씩 꺼낸 다음, 해당 증가분 중에 부피가 가장 많이 늘어나는 카드를 선택한다. 이후 해당 카드를 맞는 우선순위 큐에서 꺼내 제거한 다음, 해당 증가분 만큼 기존 좌표에 반영해 좌표를 최신화한다. 또한 동시에 답으로 출력할 문자열에 지금 카드에 대한 정보를 입력한다. 이후 탐색이 종료되고 답 문자열을 출력하면 된다.

 

public class Main {
    static long[] point = new long[4];//현재의 각 좌표 저장용
    static long[] increments = new long[4];//각 좌표 증가분

    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 K = Integer.parseInt(st.nextToken());
        StringBuilder answer = new StringBuilder();

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < 4; i++) {//좌표 저장
            point[i] = Integer.parseInt(st.nextToken());
        }

        PriorityQueue<Integer>[] pqs = new PriorityQueue[4];
        for (int i = 0; i < 4; i++) {//각 좌표에 대한 우선순위 큐 생성
            pqs[i] = new PriorityQueue<>(Collections.reverseOrder());
        }

        for (int i = 0; i < N; i++) {//카드 속 좌표, 증가분 처리 후 우선순위 큐 삽입
            st = new StringTokenizer(br.readLine());
            char c = st.nextToken().charAt(0);
            pqs[c - 'A'].add(Integer.parseInt(st.nextToken()));
        }

        for (int i = 0; i < K; i++) {
            int bestCard = 0;

            for (int j = 0; j < 4; j++) {//각 좌표의 증가분 저장
                if (!pqs[j].isEmpty()) {
                    increments[j] = pqs[j].peek();
                } else {//더 이상의 증가분이 없다면
                    increments[j] = 0;
                }
            }

            for (int j = 1; j < 4; j++) {//각 좌표에 대한 카드 중 가장 부피가 많이 늘어나는 카드 계산
                if (!pqs[j].isEmpty() && (increments[bestCard] * point[j] < increments[j] * point[bestCard])) {
                    bestCard = j;
                }
            }

            //해당 카드 좌표 우선순위 큐에서 제거 후 좌표 최신화
            pqs[bestCard].poll();
            point[bestCard] += increments[bestCard];
            answer.append((char) (bestCard + 'A') + " " + increments[bestCard] + "\n");
        }

        System.out.println(answer);
    }
}

결과