백준 21557 - 불꽃놀이 (자바 - 그리디)

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

21557번: 불꽃놀이

 

* 문제 요약

불꽃놀이는 N 개의 폭죽더미를 이용할 예정입니다.

당신은 아래 작업을 정확히 N - 2 번 반복해서 폭죽을 터뜨리려고 합니다.

- 양 끝 폭죽더미를 제외한 폭죽더미를 하나 고릅니다.

- 해당 폭죽더미의 폭죽을 모두 터뜨립니다.

- 폭발한 폭죽더미는 사라지고, 양 옆으로 가장 가까운 폭죽더미의 높이가 1씩 감소합니다.

불꽃놀이가 끝나고 나면 두 개의 폭죽더미만이 남습니다. 한 번 불꽃놀이에 사용한 폭죽더미는 재사용이 불가능하기 때문에, 남은 두 폭죽더미의 높이 중 더 큰 값을 최소화 하려고 합니다.

이 값에 찾는 프로그램을 작성해봅시다.

 

* 입력

첫 줄에는 폭죽더미의 갯수 N 이 주어집니다. 다음 줄에는 각 폭죽 더미의 높이 A1, A2, .... AN 이 주어집니다.

 

* 출력

마지막 두 폭죽더미중 더 높은 것의 높이의 최솟값을 출력합니다.

 

* 제한

- 3 <= N <= 2 * 10^5

- N <= Ai <= 10^9

 

* 예시

 

* 해결 과정

마지막에 남은 양 끝의 폭죽더미중 높이가 더 높은 푹죽더미의 높이를 최소화 시켜야 하므로 매 반복마다 양 끝의 폭죽더미중 높이가 더 높은 폭죽더미의 높이가 1씩 낮아지게끔 만들어야 한다.

기존의 양 끝의 폭죽더미의 높이가 점점 낮아지다가 사라질 경우 그 다음에 있던 폭죽더미가 자연스럽게 양 끝에 존재하는 폭죽더미로 대체된다.

 

양 끝에 있는 폭죽더미의 높이를 서로 비교하면서 터뜨릴 폭죽더미의 위치를 결정하고 원활하게 높이를 감소시켜 주기 위해 덱 자료구조를 활용했다.

매 반복마다 양 끝에 있는 폭죽더미의 높이를 비교해서 높이가 더 높은 폭죽더미를 첫번째로 잠깐 빼놓는다.

그 다음 두번째로 빼낸 폭죽더미는 덱에서 완전히 제거한다.(폭죽더미를 터뜨림)

마지막 세번째로 빼낸 폭죽더미는 첫번째 처럼 덱에서 잠깐 빼놓는다.

덱에서 잠깐 빼놓은 첫번째, 세번째 폭죽더미의 높이를 1 감소 시킨 다음 덱에서 빼낸 순서대로 다시 각 위치에 맞게 집어넣는다.

만약 높이를 1 감소 시켰을 때 높이가 0 보다 작거나 같다면 덱에 다시 집어넣지 않고 넘어간다.

 

위의 과정을 덱의 크기가 2 보다 클 때까지 반복한다.

덱의 크기가 2가 되고나면 둘 중 높이가 더 큰 값을 출력한다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Deque;
import java.util.LinkedList;

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());
        int[] fire = new int[count];

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

        Deque<Integer> fireDeque = new LinkedList<>();
        for (int i = 0; i < fire.length; i++) {
            fireDeque.offer(fire[i]);
        }

        while (fireDeque.size() > 2) {
            int first = fireDeque.peekFirst();
            int last = fireDeque.peekLast();
            boolean check = (first < last ? true : false);
            if (check) {
                int lastFire = fireDeque.pollLast();
                fireDeque.pollLast();
                int beforeFire = fireDeque.pollLast();

                beforeFire--;
                lastFire--;

                if(beforeFire > 0){
                    fireDeque.offerLast(beforeFire);
                }
                if(lastFire > 0){
                    fireDeque.offerLast(lastFire);
                }
            } else {
                int firstFire = fireDeque.pollFirst();
                fireDeque.pollFirst();
                int afterFire = fireDeque.pollFirst();

                firstFire--;
                afterFire--;

                if(afterFire > 0){
                    fireDeque.offerFirst(afterFire);
                }
                if(firstFire > 0){
                    fireDeque.offerFirst(firstFire);
                }
            }
        }

        int number1 = fireDeque.poll();
        int number2 = fireDeque.poll();

        int result = 0;
        if (fireDeque.isEmpty()) {
            result = Math.max(number1, number2);
        }

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

 

양 끝에 있는 폭죽더미 중 높이가 더 큰쪽의 높이를 최소화 시키려면 매 반복마다 양 끝에 있는 폭죽더미중 높이가 더 높은 폭죽더미가 터뜨려서 없어지는 폭죽더미의 옆에 나란히 붙어서 높이가 계속 낮아져야 한다.

매 반복마다 높이가 더 높은 폭죽더미를 찾아서 1 씩 감소시키는 방식으로 최적의 경우를 찾아서 로직을 수행하고 있으므로 그리디 알고리즘 문제에 해당된다.