[BOJ] 1654 랜선 자르기

문제

www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

풀이

랜선 길이의 최대값이 2^31 -1 이기 때문에 길이를 1부터 최대 길이까지 범위로 찾는 방식으로 풀면 시간 초과가 나올 것이다.

 

그러므로 범위를 줄여나가며 풀어야겠다고 생각했다. 찾아볼 범위의 시작을 start = 1이라 하고 범위의 끝은 end라고 했다. end는 랜선길이중 최대값 일 것이다. 중간값을 mid이라 했다.

 

mid로 k개의 랜선을 잘랐을 때 개수가 n개 이상이면 최대길이는 적어도 mid값 이상이므로 start = mid+1;

n개 이하이면  최대길이는 적어도 mid값 이하이므로 end = mid-1; 로 해준다.

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

public class Main {
	public static boolean chk_cnt(long[] lens, long leng, int N) {
		long cnt =0 ;
		for(long len : lens) {
			cnt+= len/leng;
		}
		return cnt>=N;
	}
	public static long binary_search(long[] lens, int N) {
		long result=0;
		long max_len=0;
		long start = 1, end, mid=0;
		//K개의 랜선 중 최대 길이 찾기
		for(long len : lens) {
			max_len = Math.max(max_len,len);
		}
		
		//이진 탐색 시작
		end = max_len;
		while(start<=end) {
			mid = (start+end)/2;
			if(chk_cnt(lens,mid,N)) {
				result = Math.max(result, mid);
				start = mid+1;
			}
			else {
				end = mid-1;
			}
		}
		return result;
	}
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		//선언 및 입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N,K;
		long lens[];
		st = new StringTokenizer(br.readLine());
		K = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		lens = new long[K];
		for(int i=0;i<K;i++)
			lens[i] = Integer.parseInt(br.readLine());
		
		
		//계산
		System.out.println(binary_search(lens,N));
	
	}

}