[백준] 2805: 나무 자르기 - JS (이분 탐색)

  목 차

• 문제
• 접근 방식
• 풀이

 

---

  문제

 

나무의 수 N과 필요한 나무의 길이 M이 주어진다.

두 번째 줄에는 나무의 높이가 주어진다. ex) [20, 15, 10, 17]

 

 

  접근 방식

 

아직 퀵 정렬을 배우지 않은 초보개발자로, 미비한 점이 많을 것이다. 나중에 되돌아보며 더 나은 코드로 수정할 예정이다.

 

먼저 나는 재귀 함수를 사용하기 보다는 그냥 변수에 할당해서 사용하기로 했다. (메모리 문제)

전체적인 풀이 방법은 단순하다. 값을 할당할 변수를 선언하고, 최대한 반복을 하지않기 위해 가장 큰 값을 highest 변수에 할당하고 계속 업데이트 해주려고 한다. 그리고 H 값은 커터의 높이이므로 퀵 서치 방식으로 한다.

 

 

<!! 왜 그러는지 연구해야함>

디버깅을 하다가 보니 저 종료 조건에서 for문이 제대로 작동하지 않는 현상을 발견했다. 그래서 그냥 for문을 하나 복붙하고 거기서 result 값을 초기화한 후에 더하고 그 값이 맞다면 출력하고 아니면 값을 찾을 수 없다고 출력한다. 

 

 

 

  풀이

 

백준 문제에서 이분 탐색의 키 포인트는 수많은 정답들 중에서 가장 적합한 답을 찾는 것이다.

이 다음 문제인 랜선 자르기도 그렇고, 공유기 설치 문제 역시 그렇다.

const A: number[] = [20, 10, 15, 17]

function cuter(arr: number[], M: number) {	
  let result = 0;
  let highest = Math.max(...arr);
  let H = Math.floor(highest) / 2;
  let start = 0;
  let end = highest;

  while (start <= end) {
    result = 0;  // 초기화

    for(let i = 0; i < arr.length; i++){
      if(arr[i] > H) {
        result += (arr[i] - H);  // result에 값을 더함
        
      };
    }

    if(result >= M) {
      result = H;
      start = H + 1;
    } else if(result < M) {
      end = H - 1;
    }
   	H = Math.floor((start + end) / 2);
    
  }
}


cuter(A, 10);

 

 

더 보기: 수정 전 코드

수정 전 코드

const A: number[] = [20, 15, 10, 17]

function cuter(arr: number[], M: number) {	
  let result = 0;
  let highest = Math.max(...arr);
  let H = Math.floor(highest) / 2;

  while (result !== M) {
    result = 0;  // 초기화

    for(let i = 0; i < arr.length; i++){
       if(arr[i] > H) {
         result += (arr[i] - H);  // result에 값을 더함
        
       };
    }

    if(result > M) {
      H = Math.floor((H + highest) / 2);  // 예상값 = 17
    }
		
    if(result < M) {
      highest = H;
      H = Math.floor((H - (H - highest)) / 2);  // 지금 H 값 = 17, 이전 H 값 = 15를 어떻게 하면 좋을까?
    }

    if(highest - H == 1) {
      result = 0;
      for(let i = 0; i < arr.length; i++){
        if(arr[i] > H) {
          result += (arr[i] - H);  // result에 값을 더함
        };
      };

      // 종료 조건
      if(result == M) {
        console.log(result)
      } else {
        console.log('결괏값을 찾을 수 없습니다.'); break;
      };
      
    }
    
	}
}


cuter(A, 58);