[백준] 1654 랜선 자르기 - 파라매트릭 서치(Paramatric Search) JAVA

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

1654번: 랜선 자르기

코드설명

파라매트릭 서치 문제입니다.

 

문제로직에 대한 설명입니다.

 

1. 모든 랜선의 최소값 = 1, 최대값 을 설정하여  랜선 길이의 중앙값(middle) 을 가지고 실제로 랜선을 잘라보면서, 영식이가 가져가야하는 랜선의 개수와 비교합니다. (최소값 = 1 로 설정해야지 divisionByZero Error 가 나오지 않습니다. 최소값을 0 으로 설정할경우 middle이 0 이 나오는 경우가 있습니다.)

2. 영식이가 가져가야하는 랜선의 개수보다 더 크다면, 최대 길이의 랜선을 구하는 것이 목표이므로 랜선길이를 조금씩 늘려가기 위해 start = middle + 1을 처리합니다. ( 랜선길이를 늘리다보면 어느순간 가져갈 수 있는 랜선의 개수(divideCnt)는 더 작아집니다. ) 반대의 경우는 end = middle - 1 을 처리합니다.

3. 2번의 과정을 반복하다보면, 어느순간 divideCnt가 M과 같아지게 되고, 랜선의 길이는 최대값이 됩니다.

if( divideCnt >= M) {
    start = middle + 1;
}else {
    end = middle - 1;
}

 

문제에서 겪을 수 있는 오류는 divdebyZero 문제입니다.

이떄, 처음에 아래 코드에서 (0, end)로 두었기에 divdeByZero가 발생합니다.

paramatricSearch(1, end);

랜선의 길이는 0이 될 수 없으니 1부터 시작하도록 처리할 경우 해당 문제가 해결됩니다.

 

 

 

코드

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

public class Main {
	public static int N, M, K = 0;
	public static int[] arr; 
    public static void main(String[] args) throws IOException{
    	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 int[N];
    	int end = 0;
    	for(int i=0;i<K;i++) {
    		st = new StringTokenizer(br.readLine());
    		arr[i] = Integer.parseInt(st.nextToken());
    		end = Math.max(end, arr[i]);
    	}
    	
    	paramatricSearch(1, end);
    }
    
    public static void paramatricSearch(int start, int end) {
    	long left = start;
    	long right = end;
    	
    	long sum = 0;
    	while(left <= right) {
    		long middle = (left + right) / 2;
    		
    		sum = 0;
    		for(int i=0;i<K;i++) {
    			sum += arr[i] / middle;
    		}

    		//만약 K개보다 만든게 적다면, 자르는 랜선의 길이를 감소시켜야 만들어내는 랜선의 양이 증가할 것 입니다. 
    		if(sum < N) {
    			right = middle - 1;
    		}
    		//만약 K개보다 크거나, 같게 만들었다면, 길이를 증가시킵니다.
    		else if(sum >= K) {
    			left = middle + 1;
    		}
    		
    	}
    	System.out.println(right);
    	
    }
    
    
}

 

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


public class Main {
	
	public static int N, M;
	public static long[] arr;
	public static long value = 0;
	public static long start = 0, end = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	M = Integer.parseInt(st.nextToken());
    	arr = new long[N];
    	
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		arr[i] = Long.parseLong(st.nextToken());
    		end = Math.max(end,  arr[i]);
    	}
    	paraMatricSearch();
    	
    }
    
    public static void paraMatricSearch() {
    	start = 1;
    	end = end;
    	
    	while(start <= end) {
    		long middle = ( start + end ) / 2;
    		
    		long divideCnt = 0;
    		for(int i=0;i<N;i++) {
    			divideCnt += arr[i] / middle;
    		}
    		
    		if( divideCnt >= M) {
    			start = middle + 1;
    		}else {
    			end = middle - 1;
    		}
    		
    	}
    	System.out.println(end);
    }

    
}

 

 

아래 코드의 특이사항은, 입력값이 2^31 -1 까지가 최대값이기에, 처음에 1<<31 - 1 로 처리했습니다. 이때, right = hi + 1 로 최대값의 범위를 올바르게 잡아주도록 하였지만, 작동하지 않았습니다. (작은 반레는 맞으나 계속해서 45%에서 틀렸습니다.)

제가 직접 답의 상한값을 설정하는 대신에 들어온 랜선의 길이 중 최대값을 MAX로 잡아서 진행할경우 성공적으로 작동합니다.(길이는 0부터 2^31-1 까지의 입력이 가능합니다. 그렇기에 2^31 -1  + 2^31 -1 두개 의 값이 더해질경우 INT 범위를 벗어나므로 long 형을 활용하여 값들을 처리합니다.)

 

또, 이진탐색의 동작방식의 경우, UPPER BOUND + N개의 랜선을 만들어야 한다 입니다.

UPPER BOUND는 내가 찾고자 하는 가장 적절한 랜선의 길이보다 큰 값중 가장 가까운 위치를 반환합니다.

이떄, 우리는 단순히 UPPER BOUND 값을 바로 반환한다면, 가장 적절한 랜선의 길이보다 1 더 큰 길이를 반환하기에 -1 을 처리해서, N개의 랜선을 만들어 낼 수 있는 랜선의 길이 중 최대값을 찾아낼 수 있습니다.

 

문제에서 범위 OVERFLOW(시작값은 반드시 [lo..hi] 값 중 존재하여야 합니다. 이떄 lo는 1, hi = MAX )와 파라매트릭 서치의 범위처리(UPPER BOUND에 대한 이해)가 중요했던 문제입니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	private static int N, K, M;
    private static int answer = 0;
    private static long[] arr;
    public static void main(String[] args) throws IOException {
        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];
        long max = 0;
        for(int i=0; i<K; i++) {
            arr[i] = Long.parseLong(br.readLine());
            max = Math.max(max, arr[i]);
        }
        
//        System.out.println(paramatricSearch(1, 1<<31 - 1));
        System.out.println(paramatricSearch(1, max));
    }

    private static long paramatricSearch(long lo, long hi) {
    	long left = lo;
    	long right = hi + 1;
    	
    	while(left + 1 < right) {
    		long mid = (left + right) / 2;
    		//mid길이로 랜선을 잘랐을떄, N개 이상을 만들 수 있다면, 
    		//자르는 길이를 더 길게해야 한다.
    		if( divideLanLine(mid) >= N) {
    			left = mid;
    		}else {
    			right = mid;
    		}
    	}
    	return right - 1;  
    }
    private static long divideLanLine(long length) {
    	long cnt = 0;
    	for(int i=0;i<K;i++) {
    		cnt += arr[i] / length;
    	}
    	return cnt;
    }
    
}