백준 - 2785

[Silver II] 체인 - 2785

문제 링크

성능 요약

메모리: 315992 KB, 시간: 1892 ms

분류

그리디 알고리즘, 정렬

문제 설명

희원이는 그의 다락방에서 N개의 체인을 찾았다. 각각의 체인은 몇 개의 고리로 연결되어 있는데, 각각의 고리는 최대 두 개의 인접한 고리를 가질 수 있다. 각각의 고리는 열고 닫을 수 있다. 그래서, 체인을 분리하거나 두 체인을 연결하여 하나의 긴 체인으로 만들 수 있다. 희원이는 가능한 한 적은 고리를 열고 닫아서, 모든 체인을 하나의 긴 체인으로 연결하려고 한다.

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

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

입력

첫 번째 줄에는 체인의 개수를 나타내는 양의 정수 N (2 ≤ N ≤ 500000)이 주어진다. 두 번째 줄에는 각각의 체인의 길이를 나타내는 N개의 양의 정수 L_i(1 ≤ L_i ≤ 1000000)가 주어진다.

출력

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ArrayList<Integer> list = new ArrayList<Integer>();
        int n = sc.nextInt(); // 체인의 개수
        int min = 0; // 최소한의 고리 수
        for (int i = 0; i < n; i++) {
            int length = sc.nextInt();
            list.add(length);
        }
        Collections.sort(list);
        while (list.size() > 1) {
            list.set(0, list.get(0) - 1);
            list.remove(list.size() - 1);
            if (list.get(0) == 0)
                list.remove(0);
            min++;
        }
        System.out.println(min);
    }
}