[백준 1654] 랜선 자르기_이분탐색

www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

문제풀이

• 이분 탐색으로 구현
• 정확하게 이분탐색을 알아야만 풀 수있음
• int형이아닌 long으로 받는 것이 중요 (N=1,000,000)
• 길이는 자연수라고 했으므로 min 값을 1로 잡는 것이 중요(상식적으로 길이가 0인 선은 없는 것임)

min	min	middle
1	802	401
1	400	200
201	400	300
299	201	250
201	249	225
201	224	212
201	211	206
201	205	203
201	202	201
201	200	201

 

Java

package Z_ShinHanCard_Prepare;
/*
 * 4 11
   802
   743
   457
   539
 * */
import java.io.*;
import java.util.*;
public class D3백준_랜선짜르기_이분탐색 {
	static ArrayList<Integer> arr  = new ArrayList<Integer>();
	public static void main(String[] args) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String input = br.readLine();
		StringTokenizer st = new StringTokenizer(input);
		int R = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		for(int i =0 ; i <R ; i++)
		{
			input = br.readLine();
			int temp = Integer.parseInt(input); 
			arr.add(temp);
		}
		Collections.sort(arr);
		//arr : 457 539 743 802 
		long max = arr.get(R-1); 
		long min = 1; //자연수라서 1
		long middle =0; 
		
		while(max>=min) //이분탐색
		{
			middle = (max+min)/ 2;
			long allcount =0;
			for(int i =0  ; i <arr.size(); i++)
			{
				allcount += arr.get(i) / middle; 
			}
			 
			if(allcount >= C) 
			{
				min = middle +1;
			}else if(allcount <C )
			{
				max=middle -1;
			}
				
		}
		
		System.out.println(max);
		 
		
		// TODO Auto-generated method stub

	}

}