백준 27514 - 1차원 2048 (자바 - 그리디)

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

27514번: 1차원 2048

 

* 문제 요약

2^k (0 <= k <= 62) 꼴의 정수 또는 0 으로만 이루어진 수열이 있습니다. 이 수열에 대해 다음과 같은 연산을 정의했습니다.

- ai = aj 인 서로 다른 i, j 를 골라서 ai, aj 를 각각 2ai, 0 으로 변경합니다. (이때 수열의 첫 번째 원소는 a1 입니다.)

예를 들어 수열ㅍ[2, 4, 2, 0, 1] 에 i = 1, j = 3 을 골라 실행한다면 수열은 [4, 4, 0, 0, 1] 이 되며, 여기에 i = 1, j = 2 를 골라 실행한다면 수열은 [8, 0, 0, 0, 1] 이 됩니다.

 

수열에 연산을 여러번 실행하여 수열의 최대값이 가능한 한 커지길 원합니다. 이 연산을 계속 반복했다가는 머리가 아파질 것이라고 생각하여, 여러분에게 프로그램 제작을 부탁하기로 했습니다.

수열이 주어졌을 때 정의한 연산을 0 번 이상 시행하여 수열의 최대값을 가능한 한 크게 만들어주세요

 

* 입력

첫 번째 줄에 수열의 길이 N (1 <= N <= 200,000) 이 주어집니다.

두 번째 줄에 수열의 각 원소 ai (1 <= i <= N, ai = 0 또는 2^k (0 <= k <= 62)) 가 주어집니다. 수열 a 에는 2^k 꼴의 정수가 반드시 하나 이상 존재합니다.

 

* 출력

첫 줄에 정의한 연산을 0 번 이상 수행해 만들 수 있는 가장 큰 최대값을 출력하세요. 문제의 답은 2^62 보다 크지 않음이 보장됩니다.

 

* 예시

 

* 해결 과정

데이터를 항상 오름차순으로 정렬하여 저장해두는 우선순위 큐를 활용하였다.

이를 통해 우선순위 큐에 마지막으로 남는 값이 최대값에 가까워지게끔 유도하였다.

반복문은 아래와 같이 수행하였다.

1. 우선순위 큐에서 첫 번째, 두 번째 요소를 꺼낸다.

2. 두 요소가 서로 같을 경우 두 번째 요소에 2 를 곱해준 다음, 다시 우선순위 큐에 넣어준 후 현재 최대값을 갱신해준다.

3. 두 요소가 같지 않을 경우 두 번째 요소만 우선순위 큐에 넣어준다.

위의 과정을 우선순위 큐의 크기가 1 보다 클 동안 반복한다.

 

반복 결과 우선순위 큐의 크기가 1 인 경우 현재 우선순위 큐에 남아있는 값이 최대값이므로 해당 값을 우선순위 큐에서 꺼내면서 출력해주고, 그렇지 않은 경우 현재까지 저장된 최대값을 출력해준다.

 

* 코드

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

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());
        String[] input = br.readLine().split(" ");

        PriorityQueue<Long> prior = new PriorityQueue<>();

        for (int i = 0; i < count; i++) {
            if (!input[i].equals("0")) {
                prior.offer(Long.parseLong(input[i]));
            }
        }

        long max = 0;
        while (prior.size() > 1) {
            long number1 = prior.poll();
            long number2 = prior.poll();

            if (number1 == number2) {
                max = number2 * 2;
                prior.offer(max);
            } else {
                prior.offer(number2);
            }
        }

        if (prior.size() == 1) {
            bw.write(prior.poll() + "\n");
        } else {
            bw.write(max + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

 

현재 상황에서 최적의 해답을 선택한다. -> 항상 오름차순으로 정렬되어 있는 우선순위 큐에서 가장 앞에 있는 두 값을 비교하며 로직을 수행한다.

선택된 해답이 조건을 만족하는지 검사한다. -> 우선순위 큐의 크기가 1 이하가 되기 전까지는 현재 구한 값이 최대값인지 특정할 수 없으므로 계속 반복문을 수행한다.

 

위의 과정을 통해 최대값에 가장 근접한 값을 구해냈으므로 그리디 알고리즘 문제에 해당된다.