[BOJ-1654][이분탐색] 랜선자르기 -Java

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

1654번: 랜선 자르기

package BOJ_이분탐색;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class boj_1654_랜선자르기 {
	public static void main(String[] args) throws IOException {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st =new StringTokenizer(br.readLine());
		
		long k=Long.parseLong(st.nextToken());
		long n=Long.parseLong(st.nextToken());
		long []line = new long[(int) k];
		
		long max=Long.MIN_VALUE;
		for(int i=0; i<k; i++) {
			line[i]=Long.parseLong(br.readLine());
			max = Math.max(line[i],max);
		}
		
		long result=solve(line,n,k,max);
		System.out.println(result);
	}

	private static long solve(long[] line, long n, long k, long max) {
		long left =1;
		long right=max;
		long result=Long.MIN_VALUE;
		
		while(left<=right) {
			long mid=(left+right)/2; //선의 중간 길이 
			
			if(cal(mid,line,n,k)) { //지금 선 길이로 잘랐을 때 길이보다 같거나 크다면 길이를 오른쪽으로 보냄 
				result=Math.max(mid, result);
				left=mid+1;
			}
			else right=mid-1;
		}
		return result;
	}

	private static boolean cal(long mid, long[] line, long n, long k) {
		long result=0;
		for(int i=0; i<k; i++) {
			result+=line[i]/mid;
		}
		
		if(result>=n) return true; //left를 오른쪽으로 보내서 최대값 찾아야 함
		return false;
	}

}

소요시간 : 18분

 

우선 이분 탐색 문제이고 이분 탐색을 해야 하는 목표는 자르는 랜선의 길이입니다.

 

만약 자르려고 하는 랜선의 길이를 mid라고 하면

이 mid를 통해서 자른 랜선의 갯수가 N보다 크거나 같다면 

랜선의 길이의 최댓값을 구하기 위해 left=mid+1을 줘서 더 오른쪽 부분을 탐색하게 됩니다.

 

만약 mid를 통해서 자른 랜선의 갯수가 N보다 작다면! 

랜선이 더 필요하다는 뜻입니다. 이때는 right=mid-1을 줘서 더 많은 랜선을 가질 수 있게 해 줍니다.

 

끝~