백준 - 랜선자르기 ( 1654번, JAVA )

Binary search ( https://www.acmicpc.net/problem/1654 )

풀이

• 이진탐색문제를 확실히 알아놔야 할 것 같아서 풀어보게됐다.. 근데 확실히 이진탐색은 익숙하지 않아서 어려웠다 😭 우선 이문제에서 그랬듯 "찾으려고 하는 값", "최소값", "최대값" 이렇게 세가지에 집중해서 다른 문제도 풀어보자
• 먼저 가장 찾으려는 값의 최소값인 left / 가장 큰 값인 right를 설정했다.
• 이후 최소값이 최댓값과 같거나 작은동안 찾으려는 값의 중간값인 half의 값을 바꾸면서 주어진 조건의 랜선의 개수가 나오는지 확인한다.
• 만약 cnt(랜선의 개수) 가 구하려는 n개보다 작은 경우는 랜선을 더 작게 잘라야 한다.
• 만약 그렇지 않다면 랜선을 더 크게 잘라야한다
• 최종적으로 조건에 부합하는 right 최댓값을 출력

결론

• 다른분이 푼걸 보고 테스트케이스를 넣어가며 디버깅해가면서 이분탐색에 진행과정을 파악했다😶 이분탐색을 왜 이렇게 푸는지 꼭 기억하자

package problem_solving.search;

import java.util.Arrays;
import java.util.Scanner;

public class BakeJoon_1654 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int k = Integer.parseInt(sc.next());
		int n = Integer.parseInt(sc.next());
		int [] arr = new int[k];
		for(int i= 0 ; i < arr.length;i++) {
			arr[i] = Integer.parseInt(sc.next());
		}

		Arrays.sort(arr);

		long right = arr[arr.length-1];
		long left = 1;
		long half = 0;

		while(left <= right ) {
			long cnt = 0 ; 
			half = (left+right) / 2; 

			for(int i = 0 ; i <k ; i++ ) {
				cnt+= arr[i] / half;
			}
			
			if( cnt < n ) {
				right = half-1;
			}else {
				left = half+1;
			}
		}
		System.out.println(right);

	}

}