#1654 : 랜선 자르기

풀이방법

사용된 것:

이분 탐색

 

2022.06.14

1 이상, 갖고 있는 가장 긴 랜선의 길이 이하 중에 정답이 존재한다.

이 정도 범위는 이분 탐색으로 풀었을 때 합리적인 시간 내에 해결된다.

 

그래서 이분 탐색으로 푸는데, 이때 upper_bound의 방식으로 풀었다.

upper_bound에 대한 설명은 아래 게시글에 있다.

초급 7회차 이분탐색 & 분할정복

 

upper_bound를 이용하는 이유는 다음과 같다.

이 문제의 상황을 살펴보았을 때, 정답 값 이하의 길이로 랜선을 자른다면 무조건 영식이가 요구하는 랜선 개수를 만족할 수 있다. 정답 값 이하의 수들이 모두 특정 조건을 만족하고, 정답 값 초과의 값들은 모두 특정 조건을 만족하지 않는 상황인 것이다.

따라서, 영식이가 요구하는 랜선 개수를 만족하지 못하는 가장 작은 값, 즉 정답 값을 초과하는 가장 첫 번째 값을 찾으면 된다. 그 값을 찾아서, 거기서 1을 빼면 그게 정답 값이다.

그래서 upper_bound를 활용하는 것이다.

 

코드로 짜는 방법은 다음과 같다.

탐색 범위의 시작점 start를 1로 잡고, 끝점 end는 지금 가진 가장 긴 랜선의 길이에 1을 더한 값으로 잡는다.

그리고 start<end일 동안 다음을 반복한다.

• (start+end)/2 를 mid값으로 한다.
• 가지고 있는 랜선들의 길이를 mid 값으로 일일이 나누어보면서, mid 값 길이로 랜선을 잘랐을 때 랜선 몇 개가 얻어지는지를 센다.
• 이렇게 센 값이 영식이한테 필요한 랜선 개수보다 작다면, end값을 mid로 바꾼다. 영식이에게 필요한 랜선 개수보다 크거나 같다면 mid를 범위에서 제해야 하므로 start 값을 mid+1로 바꾼다.

 

이 과정을 끝낸 뒤 start에서 1을 빼준 값을 화면에 출력하면 된다.

 

 

코드

Java(2022.06.14)

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		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[] arr = new long[k];
		
		for(int i=0; i<k; i++) {
			arr[i] = Long.parseLong(br.readLine());
		}
		
		Arrays.sort(arr);
		
		long start = 1;
		long end = arr[k-1] +1;
		
		//이분탐색하기
		while(start<end) {
			long mid = (start+end)/2;
			
			long cnt = 0;
			for(long i: arr) {
				cnt += i/mid;
			}
			
			if(cnt<n)end = mid;
			else start = mid+1;
		}
		
		//정답 출력
		System.out.print(start-1);

	}

}