[6주차_화요일] 나무 자르기

[icegosimperson]

• 사이트 : 백준(BOJ)
• 문제: 나무 자르기
• 번호: 2805

  🤔 시간복잡도 고려사항
  💡 풀이 아이디어

[Jewan1120]

🤔 시간복잡도 고려사항

• 1 ≤ N ≤ 1,000,000 → 10^6이므로 O(N logN)
• 이분 탐색 혹은 매개 변수 탐색

💡 풀이 아이디어

• 절단기에 설정할 수 있는 높이의 최댓값을 구하는 문제이므로 만족하는 특정 범위들의 최댓값 → 매개 변수 탐색
  • 매개 변수 : 설정하는 절단기의 높이
  • 결정 함수 : 설정한 높이로 모든 나무를 잘랐을 때 자른 나무 길이의 총 합이 가져가려는 나무의 길이보다 크면 true

    // 해당 절단기의 높이로 자를 수 있는 나무의 총 길이를 구하는 결정함수
    private static boolean isPossible(int param) {
    long sum = 0;
    for (int i = 0; i < n; i++)
    sum += Math.max(0, arr[i] - param); // 음수가 될 수 없기 때문에 0으로 제한
    // 자른 나무 길이의 총 합이 m 이상이면 가능
    return sum >= m;
    }

[icegosimperson]

🤔 시간복잡도 고려사항

• N <= 10^6, M<= 10^9 -> 이분 탐색 시간 복잡도를 줄여줘야함
• O(N log N)

💡 풀이 아이디어

• M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 문제 -> 매개변수 탐색
• 나무 높이를 배열로 입력받을 때 최댓값을 갱신
• UpperBound로 나무 자르기

  while(s < e){
          int m = (s+e)/2;
          long sum = 0;
          for(int height : arr){
              if(height-m >0) sum += (height - m);// 나무 자르기
          }
          if(sum < M) e = m; // 잘린 길이가 M보다 작을 시 더 절단 높이 더 낮춤
          else s = m+1;
  }

  while(s<-=e) -> UpperBound left, LowerBound -> right값 출력? UpperBound하는 경우 e-1해줘야함, lowerBound하는 경우 -1을 하지 않아도됨

[yeongleej]

🤔 시간복잡도 고려사항

• N ≤ 1,000,000
• M ≤ 2,000,000,000 => 최대 O(NlogN)까지 가능 : 이분탐색 고려

💡 풀이 아이디어

• 구해야 하는 것(mid): 절단기에 설정할 수 있는 높이의 최댓값

  • 시작값: 0
  • 끝값: 현재 나무의 길이중 가장 긴 나무의 값

• 결정문제 : 현재 설정한 높이값(mid)으로 M미터를 가져 갈 수 있는가 없는가

  • 총 잘린 나무의 길이가 M보다 작다면, 높이를 더 작게 설정해서 자른길이의 합을 늘려야 함
  • 총 잘린 나무의 길이가 M보다 크거나 같다면, 높이를 더 크게 설정해 볼 수 있음

M의 크기를 제대로 안봐서 int로 설정해줘서 계속 틀렸습니다,,,, ㅎㅎㅎ 자바는 크기에 따라 정수 타입 설정 잘하기~

[KodaHye]

🤔 시간복잡도 고려사항

• 1 <= 나무의 수 <= 1,000,000이기 떄문에 나무에 대해 2중 반복문을 진행하면 시간 초과 발생
• O(NlogN) = 19,931,568이기 때문에 NlogN 방식으로 할 수 있는 방법 고려

💡 풀이 아이디어

• 적어도 M미터의 나무를 집에 가져가기 위해 설정할 수 있는 높이의 최댓값을 구해야 됨
• 나무의 길이는 1 <= M <= 2,000,000,000이기 때문에 int 형으로 선언한다면 연산 과정에서 overflow가 발생할 수 있으므로 나무 길이와 관련된 변수는 long으로 선언해주기
• 나무 길이에 대한 누적합 저장
  • 잘린 나무들의 합을 구해야되는데, 나무 배열에 대해 1,000번 선형탐색해도 시간 초과가 발생하기 때문
  • 나무 배열이 11 22 33 44 이고, 길이 제한이 10일 경우
  • 상근이가 가져갈 수 있는 나무 길이 합: 1 + 12 + 23 + 34 = 70
  • 나무 배열 누적합: 0 11 33 66 110
    • (110 - 0) - (길이 제한) * (자른 나무의 개수)
    • (누적합에서 마지막 idx 값 - 최초 잘리는 나무 직전 idx) - (길이제한) * 자른 나무의 개수
• getUpperIdx(long[] arr, long target): 길이가 m일 때, m이 arr 배열에 있을 수 있는 가장 오른쪽 idx 반환
• long cutSum: 잘린 나무들의 합계

잘린 나무들의 합을 구할 때, 나무 배열에 대해 1,000번 선형탐색했을 때 시간 초과가 발생할 수 있다고 생각했는데, log_2(2_000_000_000)의 값이 약 31이어서 시간 초과가 발생하지 않네요!!! 제가 너무 복잡하게 생각했습니다!! ㅎㅎ

[baexxbin]

🤔 시간복잡도 고려사항

• 1 ≤ N ≤ 1,000,000 →10^6
• O(N logN) → 이분 탐색

💡 풀이 아이디어

• 이분탐색, 파라미터 서치 이용
  • 높이 최대 값: mid변수
  • 파라미터 서치: 잘린 길이가 M보다 크거나 같은가
• 절단기 높이 찾기
  • left, right 초기화: 절단기의 가능한 최소, 최대 높이 (0, 가장 높은 나무 길이)
• findIdx() : 절단기의 높이 height가 정해졌을때, 해당 높이로 자르기 시작할 나무 위치

  findIdx()로 절단기에서 잘릴 나무부터 자르도록 했으나, 그냥 if tree > h 조건으로 for문 다 도는게 깔끔할 수도

• canGet() : 높이 h로 원하는 개수 C만큼 얻을 수 있는지 판단하는 결정함수
• 주의할 점
  • left, right 초기값 잘 확인하기
  • 자바 범위 잘보기! long형!

while(left < rihgt)파였는데, 파라미터 서치할땐 while(left <= rihgt)로 두고 parm을 넣는게 안헷갈리는거 같네요ㅎ.ㅎ

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: 이분탐색
• 시간복잡도: 나무의 수 1 ≤ N ≤ 1,000,000 으로 10^6
  • 이분탐색 시 최대 O(logN)으로 탐색 가능 / 완전탐색 불가

💡 풀이 아이디어

• 이분탐색을 통해 최적의 높이 최댓값 찾기 (최솟값에서 최댓값 찾기) 가장 긴 나무길이의 중간값을 높이의 최댓값 후보로 설정하고 간격 조정하면서 최적의 값 찾기
• left <= right 나무의 길이 M에 맞춰야 하기 때문에 left와 right가 겹쳐지는 구간의 mid 값이 높이의 최댓값이 됨