[백준][BOJ-1654][자바] 랜선 자르기

www.acmicpc.net/problem/1654

1654번: 랜선 자르기

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int K = Integer.parseInt(st.nextToken());
		int N = Integer.parseInt(st.nextToken());
		long[] line = new long[K];
		
		for(int i=0; i<K; i++) {
			line[i] = Long.parseLong(br.readLine());
		}
		
		long left = 1;
		long right = Arrays.stream(line).max().getAsLong();
		long mid =0;
		long result =0;
		
		while(left <= right) {
			mid = (left+right)/2;
			long num = cutLine(mid, line);
			
			if(num>= N) {
				result = Math.max(result, mid);
				left = mid+1;
			}else {
				right = mid-1;
			}
		}
		
		System.out.println(result);
	}

	private static long cutLine(long mid, long[] line) {
		long sum = 0;
		
		for(int i =0; i<line.length; i++) {
			sum += line[i]/mid;
		}
		
		return sum;
	}
}

정리

• K를 1씩 증가시키면서 N에 맞는 조건을 찾게 되면 O(KN)이 되고 최악의 경우 10,000,000,000 만큼 반복되어 시간 초과가 난다.
• 그래서 이분 탐색으로 풀어야 하는 문제이다.
•  left의 값을 1로 두어야 하는데 만약 mid가 0이 되는 경우 0으로 나누게 되고 오류가 난다.
• mid만큼 나누고 num의 숫자가 N보다 작다면 랜선을 더 작게 짤라야 되기 때문에 right의 값을 이동시킨다.
• 반복을 하면서 N의 조건에 만족하고 최대 랜선 값을 찾으면 된다.