BOJ - 1654 랜선 자르기

leehyunjon·2022년 5월 27일

ParametricSearch boj 이분 탐색

Algorithm

목록 보기

50/162

1654 랜선 자르기 : https://www.acmicpc.net/problem/1654

Problem

Solve

Parametric Search란 조건을 만족하는 최소/최댓값을 구하는 문제(최적화 문제)를 조건의 참/거짓 여부를 판단하는 문제(결정 문제)로 변환하여 푸는 문제이다.

랜선 자르기 문제 같은 경우

최적화 문제 : N개를 만들수 있는 랜선의 최대 길이
결정 문제 : 랜선의 길이가 X일 때 랜선의 길이가 N개 이상인가?

parametric search같은 문제를 고려할 경우

이분 탐색을 수행할 변수를 가지고 함수를 세웠을때 증가 함수 또는 감소 함수여야 한다.
특정 값에 대해서 최대, 최소값에 대한 조건이 있다.
범위가 무지막지하게 크다.

인 경우 parametric search를 고려해 볼 필요가 있다.

본 문제에서 parametric search으로 접근해보자

출처

랜선의 길이와 개수를 그래프로 그려보면 랜선의 개수가 증가할때 랜선의 길이는 짧아지고 랜선의 개수가 감소할때 랜선의 길이는 증가한다.

문제에서 요구하는 랜선의 최대 길이를 X라 하고 X를 구할때(최적화 문제) N이상이면서 최대의 길이를 구하기 위해서는 랜선 길이의 최소를 start, 최대를 end로 놓고 길이가 mid일 때 자른 랜선의 개수가 N이상인가를 판단한다(결정 문제).

//길이 X를 찾는 함수
static long findLength(){
		long start = minLength;
		long end = maxLength;

		while(start<end){
			//임시 길이
            //중간 값을 짝수일때 오른쪽으로 설정하여 
            //만들수 있는 랜선의 개수가 같은 길이 중 가장 큰 길이을 찾기 위함
			long mid = (start+end+1)/2;

			//임시 길이로 N개 이상의 랜선을 만들수 있는가
            //만들수 있는 랜선이 N보다 작다면 N보다 이상이 되야하므로 mid왼쪽으로 범위를 줄여준다.
			if(lensCount(mid)<N){
				end = mid-1;
			}else{
            //만들수 있는 랜선이 N보다 크거나 같다면 mid또는 mid보다 오른쪽에 있는 길이가 최대 길이이기 때문에 mid포함해서 오른쪽으로 범위를 줄여준다.
				start = mid;
			}
		}
        //기준 포인터는 N이상의 길이를 반환해야 하므로 
        //N과 같을때의 조건을 가진 start 반환
		return start;
	}

//특정 길이로 만들수 있는 랜선 개수 반환 함수
static int lensCount(long target){
		int lenCount=0;

		for(int len : lens){
			lenCount += len/target;
		}

		return lenCount;
	}

이해가 잘 안된다면 참조한 블로그를 보고 공부하자.

Code

public class 랜선자르기 {
	static int K;
	static int N;
	static int[] lens;
	static int minLength = 1;
	static int maxLength = Integer.MAX_VALUE;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		K = Integer.parseInt(st.nextToken());
		N = Integer.parseInt(st.nextToken());
		lens = new int[K];
		for(int i=0;i<K;i++){
			st = new StringTokenizer(br.readLine());
			lens[i] = Integer.parseInt(st.nextToken());
		}

		long answer = findLength();

		bw.write(String.valueOf(answer));
		bw.flush();
		bw.close();
	}

	static long findLength(){
		long start = minLength;
		long end = maxLength;

		while(start<end){
			//임시 길이
            //중간 값을 짝수일때 오른쪽으로 설정하여 
            //만들수 있는 랜선의 개수가 같은 길이 중 가장 큰 길이을 찾기 위함
			long mid = (start+end+1)/2;

			//임시 길이로 N개 이상의 랜선을 만들수 있는가
            //만들수 있는 랜선이 N보다 작다면 N보다 이상이 되야하므로 mid왼쪽으로 범위를 줄여준다.
			if(lensCount(mid)<N){
				end = mid-1;
			}else{
            //만들수 있는 랜선이 N보다 크거나 같다면 mid또는 mid보다 오른쪽에 있는 길이가 최대 길이이기 때문에 mid포함해서 오른쪽으로 범위를 줄여준다.
				start = mid;
			}
		}
        //기준 포인터는 N이상의 길이를 반환해야 하므로 
        //N과 같을때의 조건을 가진 start 반환
		return start;
	}

	//특정 길이로 만들수 있는 랜선 개수 반환 함수
	static int lensCount(long target){
		int lenCount=0;

		for(int len : lens){
			lenCount += len/target;
		}

		return lenCount;
	}
}