나무 자르기(2805)

나무 자르기(2805)

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));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
  
    StringTokenizer st =  new StringTokenizer(br.readLine());
    
    int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken());
    
    int[] tree = new int[n];
    
    st =  new StringTokenizer(br.readLine());
    
    int high = 0;
    
    for(int i = 0; i < n; i++) {
      tree[i] = Integer.parseInt(st.nextToken());
      high = Math.max(high, tree[i]);
    }
    
    int lo = 0;
    int hi = high;
    long sum = 0;
    
    while(lo <= hi) {
      int mid = (lo+hi) / 2;
      sum = 0;
      
      for(int len : tree) {
        if(len > mid) sum += len - mid;
            if(sum > m) break;
      }
      
    // 자른 나무가 모자라다 == 더 잘라야 한다 == mid를 낮춰야 한다 == hi의 범위를 수정
    if(sum < m) hi = mid-1;
    // 자른 나무가 많다 == 덜 잘라야 한다 == mid를 높여야 한다 == lo의 범위를 수정
    else if(sum >= m) lo = mid+1;
    }
    
    sb.append(hi);

    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }
}

풀이과정

1. 이전에 랜선자르기와 유사한 문제라서 이분탐색을 생각했는데 방법이 기억나지 않아 예전 문제를 참고하였다.
2. 예제와 반례들을 대입해 보면서 문제를 풀었다
3. 하지만 코드가 직관적이지 않고 결과값을 보면서 코드를 수정했기에 직관성이 떨어졌다.
4. 이분법을 다시 찾아보고 공부하며 새로운 코드를 작성하였고, 직관성과 함께 응답시간과 메모리를 감소시킬 수 있었다.

- 성공
- 메모리 : 119300 KB
- 시간 : 532 ms

보안점

1. 이분탐색 정리
2. while에서 조건은 lo < hi 가 아닌 lo <= hi로 해야한다.
3. 이유는 lo와 hi 같을 때 ‘=’ 가 없다면 로직을 한 번 더 수행하지 않는다. lo와 hi가 역전되는 순간이 모든 경우를 탐색한 것이 된다.
4. 최대값과 최소값의 차이. 최대값을 구하는 식에서는 최종결과의 hi가 정답이 되고, 최소값을 구하는 경우는 최종결과의 lo가 정답이 된다.
5. 나무자르기의 경우 최대값을 구하는 것이다.
6. 왜냐하면, 상근이가 원하는 m의 값이 딱 나오지 않는 경우가 있기 때문이다. (본문 : “이때, 적어도 M미터의 나무를 집에 가져가기 위해서”)
7. 즉, cut 높이를 0로 하여도 상근이는 원하는 m 이상을 가져갈 수 있다.
8. 하지만 m을 가져가는 cut 높이중 최대값을 구하라고 했으므로, 최종결과의 hi가 답이 된다.