[백준] 1654 - 렌선 자르기(Java)

[백준] 1654 - 렌선 자르기(Java)

문제

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

풀이/후기

나무 자르기 문제와 비슷하지만 조금 더 쉽게 풀었다.

렌선의 길이가 커서 double과 BigInteger까지 생각했는데 그냥 long으로 풀면 되는거였다.

mid가 0인 경우 나누는 수가 0이되어 오류가 발생하는데,

start를 0이 아닌 1로 잡아주니 바로 해결되었다.

코드

package BinarySearch;

import java.io.*;
import java.util.*;

public class Problem1654 {
	
	static int K, N;
	static long[] arr;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer str = new StringTokenizer(br.readLine(), " ");
		
		K = Integer.parseInt(str.nextToken());
		N = Integer.parseInt(str.nextToken());
		arr = new long[K];
		
		long max = 0;
		for (int i=0; i<K; i++) {
			arr[i] = Long.parseLong(br.readLine());
			max = Math.max(max, arr[i]);
		}
		
		long start = 1;
		long end = max;
		long result = 0;
		
		while (start <= end) {
			long mid = (start + end) / 2;
			long sum = 0;
			
			for (int i=0; i<K; i++) {
				sum += arr[i] / mid;
			}
			
			
			if (sum >= N) {
				start = mid + 1;
				result = Math.max(result, mid);
			} else {
				end = mid - 1;
			}
		}
		
		System.out.println(result);
	}
}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/983732c6225aae2d2f9ba173c46807369002352e

참고