[백준] 2785 체인 자바(Java)

문제설명

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

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

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

 

입력

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

 

출력

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

 

 

통과한 코드 ✅

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();

        ArrayList<Integer> list=new ArrayList<Integer>();

        for(int i=0; i<n; i++){
            list.add(sc.nextInt());
        }

        if(n<=3){ // n의 개수가 3이하이면
            System.out.println(1); // 고리의 개수는 1
            return;
        }

        Collections.sort(list); // 오름차순 정렬

        int cnt=0;

        while(list.size()>1){
            list.set(0,list.get(0)-1); // 제일 작은 체인 개수 - 1
            list.remove(list.size()-1); // 큰 체인 부터 하나씩 삭제
            cnt++; // 연결되었으니 카운트 증가

            if(list.get(0)==0) list.remove(0); // 체인의 개수가 0이라면, 해당 인덱스 삭제
        }
        System.out.println(cnt);
    }
}