[백준 1654번 / JAVA] 랜선 자르기

[백준 1654번 / JAVA] 랜선 자르기코딩테스트/백준2023. 6. 22. 05:59@mag1c

Table of Contents

728x90

문제 링크

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

1654번: 랜선 자르기

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그

www.acmicpc.net

풀이

이진탐색을 활용하는 문제이다.

[알고리즘] 이진탐색(이분탐색) - Binary Search

Binary Search 정렬된 데이터 집합을 이분화 하면서 탐색하는 방법 정렬되어 있어야 한다 보통 세 개의 변수를 지정해 두고 (ex : left, mid, right) 찾고자 하는 값, 즉 mid의 값이 찾아낸 값보다 크면 mid는

mag1c.tistory.com

계속 ArithmeticException : / by zero 가 발생했는데, 이진탐색 진행 중에 mid 값이 0이 되는 경우가 발생하면 발생할 수 있기 때문에 해당 문제만 해결해 주면 된다.

또한 이진 탐색의 기준을 랜선의 길이로 생각하고 조건을 주면 쉽게 해결될 문제임.

Upper Bound를 통해 left는 N을 만족하는 최대값 + 1, 즉 N-1인 상황의 최소값을 반환하므로 left - 1을 해 주어야 한다.

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

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());
    	int[] lan = new int[K];
    	
    	long max = 0;
    	for(int i=0; i<K; i++) {
    		lan[i] = Integer.parseInt(br.readLine());
    		max = Math.max(max, lan[i]);
    	}    	
    	
    	System.out.println(binarySearch(lan, N, ++max));   	
    	
    }

	private static long binarySearch(int[] lan, int n, long max) {
		long left = 0;		
		
		while(left < max) {
			long mid = (left + max)/2;
			long total_lan = 0;

			for(int i : lan) total_lan += i/mid;			
			
			if(total_lan < n) max = mid;
			else left = mid + 1;
			
			
		}
		return left - 1;
	}
}

728x90