📝 Baekjoon 2805 문제풀이

---

💡문제 정의

이 문제는 비슷한 유형의 문제를 풀어보았다면 쉽게 해결할 수 있다.
바로 직전에 풀었던 baekjoon 2110 문제와 거의 동일하다! Binary Search(Parametric Search)를 이용하면 된다.

• baekjoon 2110 문제풀이

다만 나무의 최대 높이가 1,000,000,000이기 때문에 int가 아닌 long long int 타입으로 높이 및 배열을 선언해야 한다.

1) C

# include <stdio.h>
# include <stdlib.h>

long long int list[1000000];

int compare(const void *first, const void *second) {
  return *((long long int *)first) - *((long long int *)second);
}

int main(void) {
  int N, M;
  scanf("%d %d", &N, &M);

  for (int i = 0;i < N;i++) scanf("%lld", &list[i]);
  qsort(list, N, sizeof(long long int), compare);

  int ans;
  long long int min = 0; // 설정할 수 있는 높이의 최솟값 -> 0이면 모든 나무를 다 자르는 것
  // 4 26 40 42 46
  long long int max = list[N -1]; // 설정할 수 있는 높이의 최댓값 -> 가장 적은 양의 나무를 얻음 
  long long int cut; // 잘라서 얻은 나무의 양(높이)

  while (min <= max) {
    cut = 0;
    long long int mid = (min + max) / 2; // 절단기 높이 mid로 설정했을 때 cut이 몇이 되냐?
    for (int i = 0;i < N;i++) {
      if (list[i] > mid) cut += list[i] - mid;
    }

    if (cut >= M) {
      ans = mid;
      min = mid + 1;
    }
    else { // 만약 M미터를 얻지 못했다면 -> 절단기 높이 낮추기 
      max = mid - 1;
    }
  }

  printf("%lld\n", ans);

  return 0;
}