[Algorithm] B_search를 이용한 랜선 자르기

이번에 해결 한 문제는 B_search를 이용한 랜선자르기 문제이다. 처음에 이 문제를 봤을 때

사실 알고리즘에 대한 감이 별로 없는 상태라 해결을 못했었다. 그러나 공부를 하면서

감이 조금씩 생겨서 문제를 해결 할 수 있었다.

위에는 문제 원본이고 위 문제를 해결 할 때 제목에 써 있듯이 B_search를 사용하였다.

min 값과 max(max는 입력 받은 값 중 가장 큰 값)에 대하여 B_search를 하여 주어진 

조건을 만족하는 값중 가장 큰 값을 출력하였다.

사실 위 문제는 더 빨리 풀 수 있었는데 

mid 값에 +1 , -1을 붙여 주지 않아서 계속해서 오답이 발생하였다.

간단한 예제 지만 이런 사소한 것 하나하나 꼼꼼하게 체크해야 겠다.

코드는 아래와 같다.
package algorithm;

import java.util.Scanner;

public class a_1654 {

public static void main(String[] args) {
// TODO Auto-generated method stub
long max = 1;
long min = 1;
long result = 1;

Scanner sc = new Scanner(System.in);

int K = sc.nextInt();
long N = sc.nextLong();

long line[] = new long[K];

for (int i = 0; i < K; i++) {
line[i] =sc.nextLong();
max = Math.max(max, line[i]);
}//입력 완료

while ( min<=max) {
long mid = (max + min) / 2;
long cnt = 0;

for (int j = 0; j < K; j++) {
cnt += line[j] / mid;
}
if (cnt < N) {
max = mid-1;
} else{
result= Math.max(result, mid);
min = mid+1;
}
}
System.out.println(result);

}

}