[백준] 1654번 랜선 자르기 (이분탐색_JAVA)

모름지기 코테를 연습한다고 하면

이분 탐색 정도는 알아야지! 

 

생각보다 이분탐색 문제가,

이분탐색으로 풀어야 하는지

잘 모르겠다.

 

심지어 이분탐색으로 풀어야 하는 걸 알아도

적용하는 것이 어려웠어서

꾸준히 연습해야 할 것 같다.

 

---

문제

 

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

1654번: 랜선 자르기

 

 

 

---

설계

 

알고리즘 설계 [접근 방법] : 이분탐색

랜선의 최대 길이가 2^31-1이기 때문에 1부터 최대 값까지 탐색하기에는 시간초과가 발생할 것이다.

그러므로 최소 값과 최대 값을 비교하면서, 범위를 줄여나가는 이분탐색을 시도해야 한다!

최소 값을 1로 하고, 최대 값을 현재 내가 가지고 있는 랜선 중 가장 길이가 긴 값으로 설정한다.

그리고 최소 값과 최대 값인 중간부터 탐색하면서, k개 이상을 만들 수 있는 가장 긴 랜선의 길이를 찾는 것이다.

 

주의할 점

여기서 주의할 점은 필요한 랜선의 개수 n의 최대 값이 1,000,000 이기 때문에, 기준 길이로 자른 랜선을 더하다 보면 int보다 넘을 때가 있다. 그래서 m, mid, answer 등 관련있는 변수는 long으로 설정해주어야 한다.

 

풀이 과정

 1.

랜선의 개수 n과 필요한 개수 m를 입력받는다.

 

2.

그리고 현재 내가 가지고 있는 랜선의 길이를 입력받는다.

 

3.

최소 값 min은 1로 설정한다. 그리고 내가 가지고 있는 랜선들 중 가장 긴 랜선의 길이를 찾아서 최대 값인 max로 설정한다.

 

4.최소 값과 최대 값의 중간 값인 mid를 설정한다.그리고 현재 내가 가지고 있는 랜선을 mid값으로 자른다고 가정했을 때, 몇개의 랜선을 가질 수 있는지 result에 저장한다.

 

5.만약 result가 내가 가지고 싶은 랜선의 개수 m보다 작다면, 나는 더 작은 길이로 잘라야 하는 것이다. 그렇기 때문에 최대 값인 max를 mid-1로 변경한다.만약 result가 m보다 크거나 같다면, 길이를 더 크게 설정해도 m만큼의 개수를 얻을 수 있는지 확인해야 한다. 그렇기에 현재 reuslt값을 정답 배열인 answer과 비교해서 갱신한 후, min값을 mid+1로 설정한다.

 

6.answer를 출력한다.

 

 

---

코드

 

import java.util.*;

public class Test_1654_랜선자르기 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		//랜선의 개수와 필요한 개수 입력받기
		int n = sc.nextInt();
		Long m = sc.nextLong();
		
		//랜선의 길이 입력받기
		Long[] arr = new Long[n];
		for(int i=0; i<n; i++) {
			arr[i] = sc.nextLong();
		}
		
		//최대값 구하기
		Long min = 1L;
		Long max = 0L;
		for(int i=0; i<n; i++) {
			if(max<arr[i]) max = arr[i];
		}
		
		//이분탐색
		Long mid = (min+max)/2;
		Long answer = 0L;
		
		while(min<=max) {
			mid = (min+max)/2;
			
			int result = 0;
			for(int i=0; i<arr.length; i++) {
				result+=arr[i]/mid;
			}
			
			if(result<m) max = mid-1;
			if(m<=result) {
				answer = Math.max(answer, mid);
				min = mid+1;
			}
		}
		
		//출력
		System.out.println(answer);
	}
}

 

 

(❁´◡`❁)

끝!