[백준 2493번] 랜선 자르기 (JAVA)

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

1654번: 랜선 자르기

 

이분 탐색으로 이걸 어떻게 접근할까?

결국 이 부분을 생각해내는게 이 문제의 핵심이라고 생각한다.

 

이 문제를 풀지 못한 다수에게 이분 탐색은 배열에서 특정 index 값을 key 값으로 찾는 과정으로 알고 있을 것이다.

 

(내가 찾는 key 값) = > 반으로 쪼개고 다시 반으로 쪼개는 과정 =>  해당 인덱스 값 도출 

 

위 과정을 랜선 자르기에 도입하면?

 

(내가 찾는 랜선의 길이) =>  반으로 쪼개고 다시 반으로 쪼개는 과정 => 조건을 충족하는 최대 길이 도출

 

이러한 형식이 된다.

 

예제에서 주어진 4개의 랜선이 있다.

크게 크게 가기 위해서 가장 긴 랜선을 기준으로 하자.

 

이분 탐색에서 왼쪽, 오른쪽, 가운데 값을 잡아줬다.

bottom = 1;

top = 802;

mid = (0 + 802)/ 2 가 될 것이다.

 

bottom = 0 으로 두는 실수를 하지 말자

 

4개의 랜선을 mid 값으로 나눠서 몫을 다 더한다.

1) 목표로 하는 n 미만이면 

 

top = mid-1;

mid = (top + bottom) /2; 로 바꾸고 다시 돌려준다.

 

2) 목표로 하는 n과 같거나 크다면

몫을 다 더해서 n보다 크다면?

bottom = mid+1;

mid = (top+bottom)/2; 가 될 것이다.

여기까지는 기존 이분탐색과 같다. 기존 이분탐색을 n을 찾으면 탐색을 멈출 것이다.

하지만

 

최대 랜선 길이의 값을 구하기 위해서 기존 이분 탐색과 다른 부분은 무엇일까?

 

n을 찾게 되더라도 bottom = mid + 1 을 해준다는 것이다.

 

4 15
802
743
457
539

 

11개 자르지 말고 15개로 자른다고 해보자.

 

150으로 잘라도 15개로 잘린다. 하지만 최대 길이를 찾고 있으니깐.

 

top : 199

mid : 150

bottom : 101

(조건을 충족하더라도 bottom 을 mid+1로 올린다. 

=> 궁극적으로 n이15개인 부분을 넘기면서 넘기는 순간 이전의 mid값을 답으로 출력하는 것이다. )

 

top : 199

mid : 175

bottom : 151

 

top : 174

mid : 162

bottom : 151

 

top : 161

mid : 156

bottom : 151

 

top : 155

mid : 153

bottom : 151

 

top : 152

mid : 151

bottom : 151

 

top : 152

mid : 152

bottom : 152 (빨간색으로 해놓은 것은 n을 충족하는 경우임)

 

top : 152

mid : 152 => 반복문이 멈추기 전에 계속 result = mid로 갱신해준다.

bottom : 153   (반복문 조건 미충족으로 여기서 멈춤)

 

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

public class Main {

	static int n, k;
	static long[] arr;
	public static void main(String args[]) throws Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    k = Integer.parseInt(st.nextToken());
	    n = Integer.parseInt(st.nextToken());
	    arr = new long[k];
	    
	    for(int i = 0; i < k; i++) {
	    	arr[i] = Long.parseLong(br.readLine());
	    } 
	    
	    Arrays.sort(arr);
	    long top = arr[k-1];
	    long mid = 0;
	    long bottom = 1;
	    long result = 0;
	    
	    while(bottom <= top) {
	    	long cnt = 0;
	    	mid = (bottom+top)/2;
	    	
	    	for(int i = 0; i < k; i++) {
	    		cnt += arr[i]/mid;
	    	}
	    	
	    	System.out.println(top);
	    	System.out.println(mid);
	    	System.out.println(bottom);
	    	
	    	if(cnt >= n) {
	    		result = mid;
	    		bottom = mid+1;
	    	} else {
	    		top = mid-1;
	    	}

	    }
	    System.out.println(result);
	}
}