백준 2785 - 체인 (자바 - 그리디)

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

2785번: 체인

 

* 문제 요약

다락방에서 N개의 체인을 찾았다. 각각의 체인은 몇 개의 고리로 연결되어 있는데, 각각의 고리는 최대 두 개의 인접한 고리를 가질 수 있다.

각각의 고리는 열고 닫을 수 있다. 그래서 체인을 분리하거나 두 체인을 연결하여 하나의 긴 체인으로 만들 수 있다.

가능한 한 적은 고리를 열고 닫아서 모든 체인을 하나의 긴 체인으로 연결하려고 한다.

예를 들어 3개의 체인을 가지고 있고, 각 체인이 고리 하나로만 이루어져 있다면 그 중 하나를 열어서 나머지 두 개를 연결하고 닫으면 된다.

체인의 개수와 각각의 체인의 길이가 주어지면, 하나의 긴 체인으로 모든 체인을 묶기 위해 열고 닫아야 할 최소한의 고리 수를 찾아라.

 

* 입력

첫번째 줄에는 체인의 갯수를 나타내는 양의 정수 (2 <= N <= 500,000) 이 주어진다.

두번째 줄에는 각각의 체인의 길이를 나타내는 N 개의 양의 정수 Li (1 <= Li <= 1,000,000) 가 주어진다.

 

* 출력

첫째 줄에 필요한 고리의 최소 갯수를 출력한다.

 

* 예시

 

* 해결 과정

입력받은 체인들의 길이를 정렬해준 뒤에 길이가 가장 작은 체인을 분해하여 여러개의 고리를 만든 뒤, 이 고리들을 이용하여 다른 체인들을 연결시켜주는 방식으로 접근했다.

덱 자료구조를 활용했으며 가장 길이가 작은 체인을 맨 앞, 가장 길이가 긴 체인을 맨 뒤에 저장한 뒤 가장 앞에 있는 체인의 길이를 매 반복마다 1씩 줄이는 동시에 덱에서 가장 뒤에 있는 체인 2개를 합치는 방식으로 로직을 만들었다.

그러다 만약 덱의 크기가 1이 되면 모든 체인이 합쳐졌다는 뜻이므로 반복문을 종료시키고 지금까지 가장 길이가 작은 체인에서 하나씩 떼어내서 사용한 고리의 갯수를 출력해주는 방식으로 문제를 풀었다.

 

* 코드

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.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());
        String[] input = br.readLine().split(" ");
        int[] array = new int[count];
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < count; i++) {
            array[i] = Integer.parseInt(input[i]);
        }

        Arrays.sort(array);

        for (int i = 0; i < array.length; i++) {
            deque.offer(array[i]);
        }

        int result = 0;
        while (deque.size() > 1) {
            result++;
            int number1 = deque.pollLast();
            int number2 = deque.pollLast();
            deque.offerLast(number1 + number2);

            if (deque.size() >= 2) {
                int number = deque.pollFirst();
                if (number > 1) {
                    deque.offerFirst(number - 1);
                }
            }
        }

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

 

현재 상황에서 최적의 해답을 선택한다. -> 매 반복마다 길이가 가장 짧은 체인에서 고리를 하나씩 떼어 길이가 가장 긴 체인 2개를 서로 이어줬다.

선택한 해답이 조건을 만족하는지 검사한다. -> 체인이 모두 하나로 합쳐진 경우 반복문을 종료시키고, 그렇지 않은 경우 위의 로직을 계속 반복했다.

 

위의 과정을 통해 문제를 풀었으므로 그리디 알고리즘 문제에 해당된다.