링크

체인-2785

문제

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

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

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

입력

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

출력

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

풀이

..? 이 문제의 예제 3번을 보고 이해가 도저히 안가서 코딩도 못하고 문제 이해만 하느라 시간이 많이 흘렀다..

->예제 3 이해!

예제 입력 3에 해당하는

5
4 3 5 7 9
의 경우, 3에 해당하는 체인을 3개로 나누어서 남은 4개의 체인을 묶어주면 3번만에 끝나게 되는데, 이러한 특성이 이 문제의 핵심이다.

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class practice {
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int n=Integer.parseInt(br.readLine()); //체인의 개수
		int cnt=0;
		ArrayList<Integer> list=new ArrayList<Integer>();
		
		StringTokenizer st=new StringTokenizer(br.readLine());
		
		for(int i=0; i<n; i++)
			list.add(Integer.parseInt(st.nextToken()));
		
		Collections.sort(list);
		
		while(true)
		{
			if(list.size()<=1)
				break;
			list.set(0, list.get(0)-1);
			list.remove(list.size()-1); //인덱스 갑 삽입
			if(list.get(0)==0)
				list.remove(0); //인덱스 값 삽입
			
			cnt++;
		}
		
		System.out.println(cnt);
	}
}