본문 바로가기

Algorithms/Baekjoon

[Java] 백준 알고리즘 1654번 문제 (이분 탐색)

728x90

---문제---

---코드---

import java.util.Arrays;
import java.util.Scanner;
public class Bj1654 {
	public static long max_result;
	public static long[] lines;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int K = sc.nextInt();
		long N = sc.nextInt();
		lines = new long[K];
		for(int i=0; i<K; ++i) {
			lines[i] = sc.nextInt();
		}
		sc.close(); sc= null;
		Arrays.sort(lines);
		if(N==1) {
			System.out.println(lines[K-1]);
			return;
		}
		else if(K==1) {
			System.out.println(lines[K-1]/N);
			return;
		}
		else if(N==2) {
			System.out.println((lines[K-1]/2 > lines[K-2])? lines[K-1]/2 : lines[K-2]);
			return;
		}
		else {
			long left = lines[K-1]/N ;
			long right = lines[K-2]+1;
			max_result = 0 ;
			if(left>=right) {
				System.out.println(left);
				return;
			}
			
			while(left<=right) {
				long half = (left+right)/(long)2;
				if(half==0) half = 1;
				long sum = 0 ;
				for(int i=0; i<K; ++i) {
					sum += lines[i]/half;
				}
				if(sum<N) {
					right = --half;

				}else {
					if(half>max_result) {
						max_result = half;
					}
					left = ++half; 
				}
			}
		}
		System.out.println(max_result);
	}
	

}

기본적인 방식은, 제일 큰 원소를 N으로 나눈 값 (가능한 최소 후보) 과 두번째로 제일 큰 원소 (가능한 최대 후보) 를 범위로 두고

이분탐색을 진행하는 것입니다.

그러나 이 범위 경계를 만드는 과정에서 제일 큰 원소를 N으로 나눈 값이 두번째로 큰 값보다 크다면 ( if(left>=right) )

이분탐색을 할 필요가 없으므로 바로 제일 큰 원소를 N으로 나눈 값을 출력하면 됩니다.

이분탐색은, 가능 범위가 없어질 때 까지, left 와 right의 중간값을 구해서 가능한 갯수를 구하는 식입니다.

이 문제에서 가장 주의할 점은 2가지가 있습니다. (이 때문에 런타임 에러가 날 수 있습니다.)

첫번째는, 정수형 타입의 문제입니다.

half 를 구하는 과정에서 left = 1,100,000,000 right = 2,100,000,000 인 경우

left + right = 3,200,000,000 가 되는데 이는 int형의 최댓값을 훌쩍 넘는 값이므로 overflow가 나서

half의 값이 이상하게 나타나질 수 있기 때문에, 가능한 타입은 long 타입으로 해야합니다.

두번째는, half가 0이 되는 경우 입니다.

left = 0 , right = 1 인 경우 half = 0이 되기 때문에

sum 을 구하는 경우에서 0으로 나누게 되므로, 런타임 에러가 납니다.

따라서 half가 0이면 1로 바꿔주는 작업을 해야합니다.

 

---출처---

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

 

1654번: 랜선 자르기

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.

www.acmicpc.net

 

반응형