문제
-
영식이가 가지고 있는 K개의 랜선들을 잘라서 N개의 랜선을 만들 것인데, N개를 만들 수 있는 랜선의 최대 길이를 구하는 문제
-
이 문제를 해결하기 위해선 크게 두 가지 개념에 대한 이해그 필요하다
1. Upper Bound 개념
2. 이진 탐색 개념
Upper Bound 개념
-
Upper Bound 개념은 주어진 조건을 만족하는 값 중에서 가장 작은 값을 찾는 방법이다. 이 개념은 이진 탐색을 활용하여 효율적으로 수행된다.
-
이 문제에서는 중복 값이 존재하기 때문에 Lower Bound 가 아닌 Upper Bound 개념을 사용하는 것이다.
-
예를 들어 arr{1,2,2,2,3} 이라고 할때 key의 값은 2이고 Upper Bound로 찾는다면 2를 초과하는 처음 위치인 arr[4] = 3인 인덱스 4가 반한 될 것이고 여기서 -1을 해주면 key값을 찾을 수 있다.
-
하지만 Lower Bound로 찾게 된다면 2 이상 위치 중 처음 위치인 arr[1] = 2인 인덱스 1이 반환 되는 것이다.
-
이 문제에 적용한다면 198cm로 자를 때도 11개, 199,200로 자를 때 모두 동일하다 이렇게 자른 개수가 중복 되지만 최대 길이를 찾기 위해서는 특정 개수를 초과한 첫 길이에서 -1을 해주면 된다.
-
예를 들자면 본문의 입력 예제에서 계속해서 count의 값이 N보다 작아서 mid 값을 반으로 줄이고 줄여서 mid = (min + max)/ 2 = 201이 되었다고 해보자,
-
각 랜선을 201 길이로 잘라서 얻을 수 있는 랜선의 개수(count):
-
802 / 201 = 3
-
743 / 201 = 3
-
457 / 201 = 2
-
539 / 201 = 2
-
101 / 201 = 0
-
총 count = 10
-
count < N이므로 max = mid = 201
-
이 과정에서 min이 201이고 max가 201이 되며 탐색이 종료 된다 최종적으로 min - 1 = 200이 최대 랜선 길이가 되는데 이 말은 즉, 201은 랜선을 10개로 자를 때 만들 수 있는 최소 길이 이기 때문에 -1을 해주면 11개로 만들 수 있는 최대 길이가 성립되는 것이다.
구현
package Silver_2;
import java.util.Scanner;
public class Cut_LAN {
public static void main(String[] args) {
//백준 1654
Scanner sc = new Scanner(System.in);
int K = sc.nextInt();
int N = sc.nextInt();
int [] arr = new int[K];
long max = 0;
for(int i = 0; i<K; i++){
arr[i] = sc.nextInt();
if(max < arr[i]){
max = arr[i];
}
}
max ++;
long min = 0;
long mid = 0;
while(min < max ){
mid = (max + min)/2;
long count = 0;
for(int i = 0; i<arr.length; i++){
count += (arr[i] / mid);
}
/*mid 길이로 잘랐을 때의 개수가 만들고자 하는 랜선의 개수보다 작다면 자르고자 하는 길이를 줄이기 위해
* 최대 길이를 줄여서 다시 mid를 계산, 그 외에는자르고자 하는 길이를 늘려야 하므로 최소 길이를 늘린다.*/
if(count < N){
max = mid;
}
else{
min = mid + 1;
}
}
System.out.println(min -1);
}-
중간 값 계산 mid = (min + max) /2
-
조건 검사 및 범위 조정
-
count 는 mid의 길이로 랜선을 잘랐을 때 만들 수 있는 랜선의 개수.
-
만약 count가 N 보다 작으면, mid 길이로는 충분한 랜선을 만들 수 없으므로 max 를 mid로 설정하여 더 많은 랜선을 만들 수 있게 끔 만들고,
-
만약 count 가 N 이상이면 mid 길이로는 충분한 랜선을 만들 수 있으므로 더 긴 랜선을 만들 수 있는 지 확인하기 위해 min을 mid +1로 설정
-
마지막으로 이진 탐색의 특성상 탐색 범위를 점점 좁혀가며 최종적으로 min이 max에 도달할 때 까지 이 과정을 반복한다.
