[BOJ] 1654 - 랜선 자르기 (Java)

알고리즘

• 이분 탐색
• 매개 변수 탐색

1. 문제

2. Idea

• Upper Bound 이분탐색

  Upper Bound

  어진 조건을 만족하는 가장 큰 값을 찾는 방법
  이 문제에서는 랜선의 길이를 어떤 값으로 잘랐을 때 얻어지는 랜선의 개수가
  주어진 필요한 랜선의 개수보다 작거나 같아야 하기 때문에 upper bound를 사용

3. 풀이

3.1. 랜선 길이 입력 및 최대 길이 갱신

• K: 입력받은 랜선 개수
• N: 필요한 랜선의 개수
• arr: 각 랜선의 길이가 저장된 배열
• 랜선의 길이를 입력받으면서 동시에 최대 길이 갱신

Scanner in = new Scanner(System.in);

int K = in.nextInt();
int N = in.nextInt();

int[] arr = new int[K];

long max = 0;

// 입력 + max 갱신
for (int i = 0; i < K; i++) {
	arr[i] = in.nextInt();
	if(max < arr[i]) { max = arr[i]; }
}

3.2. 이분 탐색을 통한 랜선 길이 찾기:

• max: 최대 길이 + 1
• count: 현재 중간 길이로 잘랐을 때 얻어진 랜선의 개수
• 각 랜선의 길이를 mid로 나누어 얻은 몫을 count에 더해준다.
• n_length=n의 자릿수 -> 분해합을 계산할 범위 설정
• count가 필요한 랜선의 개수 N보다 작은 경우(mid 길이로 랜선을 잘랐을 때 얻어지는 랜선의 개수가 부족한 경우)
  • 최대 길이를 줄이기 위해 max = mid 수행
  • 그 외(mid 길이로 랜선을 잘랐을 때 얻어지는 랜선의 개수가 충분하거나 초과인 경우)에는 최소 길이를 늘리기 위해 min = mid + 1 수행

// 반드시 max에서 +1 값이어야 함
max++;

long min = 0; // 탐색 길이의 최솟값
long mid = 0;

while (min < max) {
  // 범위 내에서 중간 길이를 구함
  mid = (max + min) / 2;

  long count = 0;

  // 구해진 중간 길이로 잘라서 총 랜선 개수 확인

  // Upper bound 형식의 이분탐색 사용
  // mid 길이로 잘랐을 때의 개수가 만들고자 하는 랜선의 개수보다 작다면 -> 자르고자 하는 길이를 줄이기 위해 최대 길이를 줄인다.
  // 그 외에는 자르고자 하는 길이를 늘려야 하므로 최소 길이를 늘린다.
  for (int i = 0; i < arr.length; i++) {
  	count += (arr[i] / mid);
  }

  if(count < N) { max = mid; }
  else { min = mid + 1; }
}

3.3. 결과 출력

• 최종적으로 min에는 주어진 조건을 만족하는 최대 길이 + 1이 저장되어 있으므로 min-1을 최종 결과로 출력

// UpperBound로 얻어진 값(min) -1 -> 최대 길이
System.out.println(min - 1);

4. 전체코드

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int K = in.nextInt();
        int N = in.nextInt();

        int[] arr = new int[K];

        long max = 0;

        // 입력 + max 갱신
        for (int i = 0; i < K; i++) {
            arr[i] = in.nextInt();
            if(max < arr[i]) { max = arr[i]; }
        }

        // 반드시 max에서 +1 값이어야 함
        max++;

        long min = 0; // 탐색 길이의 최솟값
        long mid = 0;

        while (min < max) {
            // 범위 내에서 중간 길이를 구함
            mid = (max + min) / 2;
            
            long count = 0;

            // 구해진 중간 길이로 잘라서 총 랜선 개수 확인

            // Upper bound 형식의 이분탐색 사용
            // mid 길이로 잘랐을 때의 개수가 만들고자 하는 랜선의 개수보다 작다면 -> 자르고자 하는 길이를 줄이기 위해 최대 길이를 줄인다.
            // 그 외에는 자르고자 하는 길이를 늘려야 하므로 최소 길이를 늘린다.
            for (int i = 0; i < arr.length; i++) {
                count += (arr[i] / mid);
            }
            
            if(count < N) { max = mid; }
            else { min = mid + 1; }
        }
        // UpperBound로 얻어진 값(min) -1 -> 최대 길이
        System.out.println(min - 1);
    }
}