[백준(Baekjoon)][자바(java)] 1654 : 랜선 자르기 / 이분 탐색

 

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

1654번: 랜선 자르기

 

예제 입력 1

4 11

802

743

457

539

 

예제 출력 1

200

 

힌트

802cm 랜선에서 4개, 743cm 랜선에서 3개, 457cm 랜선에서 2개, 539cm 랜선에서 2개를 잘라내 모두 11개를 만들 수 있다.

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int k = sc.nextInt(), n = sc.nextInt(), i;
		long l[] = new long[k], max = 0, l_max = 0;
		for( i = 0; i < k; i++ ) {
			l[i] = sc.nextLong();
			l_max = l_max < l[i] ? l[i] : l_max;
		}
		sc.close();
		
		long low = 1, high = l_max, mid;  int res;
	    while( low <= high ) {
	    	mid = ( low + high ) / 2;
	       	res = 0;
	        for( i = 0; i < k; i++ )
	          	 res += l[i] / mid;
	        if( res >= n ) {
	        	low = mid + 1;
	            max = max < mid ? mid : max;
	        }
	        else
	        	high = mid - 1;
	    }

	    System.out.println( max );
        
	}
}

( 코드 참고 : https://wootool.tistory.com/114 )

 

-  low, high => n개를 만들 수 있는 랜선의 최대 길이( 구하고자 하는 답 )가 될 수 있는 구간의 하한선과 상한선

-  배열에 랜선의 길이들을 입력받음 ( long  l[0...k-1] ). 그와 동시에 가장 긴 랜선의 길이를 구함 ( long  l_max )

-  문제에서 '랜선의 길이는 2^31-1보다 작거나 같은 자연수' 라고 했으므로 만들 수 있는 랜선의 길이는 1 ~ l_max

-  [ low, high ] 구간에서 mid를 구함

-  각 랜선( l[i] )에서 mid을 나눈 값을 더하면 mid cm씩 잘랐을 때 만들 수 있는 총 랜선의 개수가 나옴 ( int  res )

-  res가 n( 필요한 랜선의 개수 ) 보다 크거나 같으면 low는 mid+1로 변경하여 탐색 범위를 줄여감. 

   또한 문제의 조건을 만족하므로 mid는 정답이 될 수 있는 가능성이 있음 ( 그 중 가장 큰 값을 구해야 함 )

-  res가 n보다 작으면 high는 mid-1로 변경하여 탐색 범위를 줄여감  ( low가 high보다 작거나 같을 때까지 반복 )