[백준] 2343 기타 레슨 - 파라매트릭 서치(Paramatric Search) JAVA

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

2343번: 기타 레슨

코드설명

파라매트릭 서치, 이분탐색 문제입니다.

 

매개변수로 블루레이 녹화시 녹화가능한 길이를 선언합니다.

최대값에는 100000 * 10000 입니다.

최소값에는 기본적으로 모든 강의 동영상이 블루레이에 들어가야하므로 강의 동영상의 최대값을 최소값을 넣어주어야만 합니다. ( 처음에는 ParamatricSearch(0, MAX)값으로 선언하여 블루레이의 최소 길이를 0 이 선언됨으로써 올바르게 계산되지 않았습니다. )

int start = 0;
int max = 100000 * 10000; //강의 동영상의 최대길이입니다.

st = new StringTokenizer(br.readLine());
arr = new int[N];
for(int i=0;i<N;i++) {
    arr[i] = Integer.parseInt(st.nextToken());
    start = Math.max(start,  arr[i]);
}	
//강의 동영상의 최대길이를 기준으로 
paramatricSearch(start, max);

 

블루레이의 길이를 기준으로 강의 동영상을 만들어서 넣을때의 로직입니다.

블루레이의 영상개수가 M개 이하라면 계속해서 영상길이를 end = mid - 1 로 바꿔주어 영상길이를 줄여주고,

M개 초과라면 영상길이를 start = mid + 1 로 영상길이를 늘려줍니다.

public static void paramatricSearch(int start, int end) {

    while(start <= end) {
        int mid = (start + end) / 2;

        int bluRayCnt = 1;
        int sum = 0;
        for(int i=0;i<N;i++) {
            sum += arr[i];
            if(sum > mid) {
                sum = arr[i];
                bluRayCnt += 1;
            }
        }
//			System.out.println("mid:"+mid+"    blurRayCnt:"+bluRayCnt);
        //만약 블루레이 동영상의 개수가 M개보다 적다면, 최소값을 찾기 위해 영상의 길이를 줄입니다.
        if(bluRayCnt <= M) {
            end = mid - 1;
        }else if(bluRayCnt > M) { //만약 블루레이 동영상의 개수가 M개보다 많다면, 동영상의 길이를 줄여야합니다.
            start = mid + 1;
        }
    }

 

또 다르게도 구현했었는데요, 결정함수를 만들어서 구현하는 과정에서 문제가 발생했었습니다.

애초에 주어진 value값, 즉 주어진 블루레이의 길이값으로 어떤 비디오 자체를 담지 못하는 경우가 있을 수 있습니다.

그러므로 아래와 같이 바로 중단해줍니다.

if(arr[i] > value) return false;

//만약 해당 블루에이 value길이를 가지고서 M개 이하의 동영상을 만들 수 있다면 true를 반환한다.
//이걸 계속반복하며 결국에는 cnt가 M과 가장 가까워지며, 결국 cnt = M이 될 것 입니다.
static boolean decision(long value) {
    int cnt = 0, length = 0;
    for(int i=0; i<N; i++) {
        if(arr[i] > value) return false;
        if(length + arr[i] <= value) {
            length += arr[i];
        }else {
            length = arr[i];
            cnt += 1;
        }
    }

    if(length <= value) {
        cnt += 1;
        length = 0;
    }

    return cnt <= M;
}

 

코드

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

public class Main {
	
	public static int N, M, H;
	public static int answer = 0;
	public static int[] arr;
	public static int[] prefixSum;
	
	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());

    	int start = 0;
    	int max = 100000 * 10000; //강의 동영상의 최대길이입니다.
    	
    	st = new StringTokenizer(br.readLine());
    	arr = new int[N];
    	for(int i=0;i<N;i++) {
    		arr[i] = Integer.parseInt(st.nextToken());
    		start = Math.max(start,  arr[i]);
    	}	
    	//강의 동영상의 최대길이를 기준으로 
    	paramatricSearch(start, max); 
    	
	}
	
	public static void paramatricSearch(int start, int end) {
		
		while(start <= end) {
			int mid = (start + end) / 2;
			
			int bluRayCnt = 1;
			int sum = 0;
			for(int i=0;i<N;i++) {
				sum += arr[i];
				if(sum > mid) {
					sum = arr[i];
					bluRayCnt += 1;
				}
			}
//			System.out.println("mid:"+mid+"    blurRayCnt:"+bluRayCnt);
			//만약 블루레이 동영상의 개수가 M개보다 적다면, 최소값을 찾기 위해 영상의 길이를 줄입니다.
			if(bluRayCnt <= M) {
				end = mid - 1;
			}else if(bluRayCnt > M) { //만약 블루레이 동영상의 개수가 M개보다 많다면, 동영상의 길이를 줄여야합니다.
				start = mid + 1;
			}
		}
		
		System.out.println(start);
		
		
	}
}

 

정답코드2입니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, A, B, X, L, R, C, n, k, m, l, K, D, T;
	static int answer = 0;
	static int[] arr = new int[100001];
	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());
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		System.out.println(optimize(1, 10000000001L));
		
	}
	static long optimize(long lo, long hi) {
		long left = lo - 1; //블루레이의 최소길이 범위
		long right = hi + 1; //블루레이의 최대길이 범위
		
		while(left + 1 < right) {
			long mid = (left + right)/2; //블루레이의 중간값
			if(decision(mid) == true) { //만약 mid 블루레이값으로 M개의 강의를 만들 수 잇다면, 블루레이의 크기를 줄여준다.
				right = mid;
			}else { //만약 불가능하다면, 블루레이의 크기를 늘려야한다.
				left = mid;
			}
		}
		return right; //lowerbound이므로 right를 최소값으로 그대로 반환한다.
	}
	
	//만약 해당 블루에이 value길이를 가지고서 M개 이하의 동영상을 만들 수 있다면 true를 반환한다.
	//이걸 계속반복하며 결국에는 cnt가 M과 가장 가까워지며, 결국 cnt = M이 될 것 입니다.
	static boolean decision(long value) {
		int cnt = 0, length = 0;
		for(int i=0; i<N; i++) {
			if(arr[i] > value) return false;
			if(length + arr[i] <= value) {
				length += arr[i];
			}else {
				length = arr[i];
				cnt += 1;
			}
		}
		
		if(length <= value) {
			cnt += 1;
			length = 0;
		}
		
		return cnt <= M;
	}
	
	
}