단계별로 풀어보기(이분 탐색 - 랜선 자르기)

1654번: 랜선 자르기 (acmicpc.net)

1654번: 랜선 자르기

http://boj.kr/9d4082dac4c1424b9bce4475f3568c31

공유 소스 보기

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

class Main{
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		
		String[] input = br.readLine().split(" ");
		
		long makeLanCable, max = 0, mid, min;
		
		int[] lan = new int[Integer.parseInt(input[0])];
		
		for(int i = 0; i < Integer.parseInt(input[0]); i++) {
			
			lan[i] = Integer.parseInt(br.readLine());
			if(lan[i] > max)  max = lan[i];
			
		}
		
		
		mid = 0;
		min = 1;
		
		while(min <= max) {
			
			makeLanCable = 0;
			
			mid = (max + min) / 2;
			
			for(int i = 0; i < lan.length; i++) {
				
				makeLanCable += lan[i] / mid;
				
			}
			
			if(makeLanCable < Integer.parseInt(input[1])) {
				
				max = mid - 1;
				
			}else {
				
				min = mid + 1;
				
			}
			
		}

		bw.write(String.valueOf((max)));
		bw.close();

    }
    
}

 

처음에는 어.., 쉽네? 하고

 

대충 시작점을 찾아서 했는데

 

시간 초과도 뜨고 틀렸습니다도 떴다...

 

그냥 직관적으로 생각했을 때

 

내 생각에는 전체의 길이의 합에서 구하고자 하는 길이를

 

나눠준 수와 가장 짧은 랜선의 길이 중 작은 것을

 

시작점으로 잡으면 되지 않을까 하고 생각했다.

 

근데 나중에 생각해보니까 가장 짧은 랜선은

 

사용하지 않아도 문제가 해결되는 경우가 있는 걸 알았고

 

다른 방식으로 접근해야겠다고 생각했다.

 

다음 방법은 가장 큰 랜선의 길이로 시작해서

 

얘를 1/2 하면서 필요한 랜선의 수가 만들어지지 않으면

 

될 때까지 1/2 하게 했으나 얘도 시간 초과가 나왔다

 

결국 알고리즘 분류를 확인했는데

 

이분 탐색이라길래 접근 방식은 비슷한 거 같은데

 

왜 안 되는 거지 하면서 검색해봤다

 

검색한 결과 여러 코드를 찾아볼 수 있었는데

 

왠지 얘는 머리에 잘 그려지지 않아서

 

한 2시간 동안 생각한 것 같다..

 

지금도 그렇게 막 와닿지는 않지만 sysout 찍어본 결과

 

무슨 느낌인지는 알겠다.

 

언젠가는 완전히 이해가 되겠지...