이진탐색 떡복이 떡 만들기

버퍼로 푸는 방법인데, 2번째는 while로 3번째는 따로 함수를 구현해서 하는 방법이다.

결론적으로는 while문을 이용해서 문제를 구현한다.

import java.util.*;

public class Main {
	public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
        
        // 떡의 개수(N)와 요청한 떡의 길이(M)
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        // 각 떡의 개별 높이 정보
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
        	arr[i] = sc.nextInt();
        }
        
        // 이진 탐색을 위한 시작점과 끝점 설정
        int start = 0;
        int end = (int) 1e9;
        // 이진 탐색 수행 (반복적)
        int result = 0;
        while (start <= end) {
        	long total = 0;
            int mid = (start + end) / 2;
            for (int i = 0; i < n; i++) {
            	// 잘랐을 때의 떡의 양 계산
                if (arr[i] > mid) total += arr[i] - mid;
            }
            if (total < m) { // 떡의 양이 부족한 경우 더 많이 자르기(왼쪽 부분 탐색)
            	end = mid - 1;
            } else { // 떡의 양이 충분한 경우 덜 자르기(오른쪽 부분 탐색)
            	result = mid; // 최대한 덜 잘랐을 때가 정답이므로 여기서 result에 기록
                start = mid + 1;
            }
        }
         System.out.println(result);
    }
}

import java.io.*;
import java.util.*;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    
    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());
    int[] arr = new int[N];
    
    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());

    int start = 0;
    int end = (int) 1e9;

    int result = 0;
    while (start <= end) {
      long total = 0;
      int mid = (start + end) / 2;

      for (int i = 0; i < N; i++) {
        if (arr[i] > mid) total += (arr[i] - mid);
      }

      if (total < M) end = mid - 1;
      else {
        result = mid;
        start = mid + 1;
      }
    }

    System.out.println(result);
  }
}

import java.util.*;
import java.io.*;

public class Main {

  public static int binarySearch(int[] arr, int target, int start, int end) {
    int result = 0;

    while (start <= end) {
      long total = 0;
      int mid = (start + end) / 2;
      
      for (int i = 0; i < arr.length; i++) {
        if (arr[i] > mid) total += (arr[i] - mid);
      }

      if (total < target) end = mid - 1;
      else {
        result = mid;
        start = mid + 1;
      }
    }

    return result;
  }

  
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    ArrayList<Integer> list = new ArrayList<>();
    
    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());

    st = new StringTokenizer(br.readLine());
    for (int i = 0; i < N; i++) list.add(Integer.parseInt(st.nextToken()));

    Collections.sort(list);
    int answer = binarySearch(list.stream().mapToInt(i -> i).toArray(), M, 0, list.get(N - 1));
    
    System.out.println(answer);
  }
}

참조

https://sogogi1000inbun.tistory.com/m/169
.
https://velog.io/@hwaya2828/2021-%EC%9D%B4%EC%BD%94%ED%85%8C-5.-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89
.