[BOJ - 2805] 나무 자르기

• 문제 조건을 제대로 읽지 않아서, "왜 틀렸지?" 하는 문제였었다... 다음부터 문제를 제대로 읽자!!

문제 링크

나무 자르기

---

---

코드

  #include <iostream>

  using namespace std;
  typedef long long int INT;
  void SearchWood(INT N, INT M, INT* H, INT max);
  INT checkMid(INT mid, INT* H,INT N,INT M);

  int main(void){

    INT N,M , max = 0;
    cin >> N >> M;

    INT* H= new INT[N];
    for(INT i=0;i<N;i++){
      cin >> H[i];
      if(max < H[i]){
        max = H[i];
      }
    }

    SearchWood(N, M, H, max);


    return 0;
  }

  void SearchWood(INT N, INT M, INT* H,INT max){
    INT left = 1;
    INT right = max;
    INT mid;
    INT Max_wood = 0;

    while(left<=right){
      mid = (left+right)/2;

      if(checkMid(mid,H,N,M)){
        Max_wood = mid;
        left = mid+1;
      }
      else{
        right = mid-1;
      }
    }
    cout << Max_wood;
  }

  INT checkMid(INT mid,INT* H,INT N,INT M){
    INT sum=0;
    for(INT i =0;i<N;i++){
      sum += (H[i]-mid >0 ? H[i]-mid:0);
    }
    return (sum>=M);
  }

---

---

풀이

  #include <iostream>

  using namespace std;
  typedef long long int INT;
  void SearchWood(INT N, INT M, INT* H, INT max);
  INT checkMid(INT mid, INT* H,INT N,INT M);

  int main(void){

    INT N,M , max = 0;
    cin >> N >> M;

    INT* H= new INT[N];
    for(INT i=0;i<N;i++){
      cin >> H[i];
      if(max < H[i]){
        max = H[i];
      }
    }

    SearchWood(N, M, H, max);


    return 0;
  }

• 조건에서 사용하는 숫자가 2,000,000,000 까지 될 수 있으므로 long long int를 사용해야 했다
• SearchWood 라는 함수를 통해 이분탐색을 이용하여 최댓값을 구한다.
• checkMid 라는 함수를 통해 mid를 이용해 sum이 M 이상이 되는지 구하는 함수다.

---

  void SearchWood(INT N, INT M, INT* H,INT max){
    INT left = 1;
    INT right = max;
    INT mid;
    INT Max_wood = 0;

    while(left<=right){
      mid = (left+right)/2;

      if(checkMid(mid,H,N,M)){
        Max_wood = mid;
        left = mid+1;
      }
      else{
        right = mid-1;
      }
    }
    cout << Max_wood;
  }

• left는 나무의 길이 중에서 최소가 1이 될 수 있으므로 1로 지정하였다.
• right는 H에서 가장 긴 것으로 지정하였고, 이유는 그것보다 커지게 되면 M만큼은 절대 구할 수 없기 때문
• 만약 M을 구할 수 있었으면 left를 옮겨준다. 그리고 if문이 없는 이유는 left를 mid보다 크게 지정하기 때문에 굳이 넣을 필요가 없어진다.
• 만약 checkmid를 할 수 없으면 right를 옮겨준다.

---

  INT checkMid(INT mid,INT* H,INT N,INT M){
    INT sum=0;
    for(INT i =0;i<N;i++){
      sum += (H[i]-mid >0 ? H[i]-mid:0);
    }
    return (sum>=M);
  }

• sum을 구하는 함수고 만약 sum이 M보다 크거나 같으면 true를 리턴해준다