[백준] 1654: 랜선 자르기 - JS (이분 탐색)

  목 차

• 문제
• 접근 방식
• 풀이

 

---

  문제

 

 

예시로 

const 랜선: number[] = [802, 743, 457, 539] 이렇게 랜선 4개가 있다면 여기서 랜선 11개를 가져가야 할 때 최대로 자를 수 있는 길이를 구하라는 것이다.

 

 

  접근 방식

 

일단 나무 자르기와 비슷한 방식으로 접근하기로 했다. 

아래는 코드 설계 전 내가 설계할 코드의 큰 틀을 설계한 것들이다.

 

 

최댓값 = max

최솟값 = min

반 값 = half

for문: 전체적인 계산 처리를 하는 코드

result = for문에서 계산된 결과가 N과 같다면 result 변수에 저장한다. 단, result 변수의 초기값은 0으로 시작하고, 최대의 값을 구해야 하므로 result의 값 보다 큰 경우 갱신하도록 한다.

 

 

  풀이

 

tamp >= N 일 때 result에 half 값을 할당하는 이유는, half 값이 어차피 계속 커지기 때문에 이렇게 작성하는 것이다.

 

	const N = 11;
	const lines = [802, 743, 457, 539];

	function cut(arr: number [], N: number) {
	let max = Math.max(...arr);
	let min = 1;
	let result = 0;

	while(min <= max) {
    let half = Math.floor((min + max) / 2);
    let tamp = 0;

		for (let i = 0; i < arr.length; i++){
     		 tamp += Math.floor(arr[i] / half);
		}

		if(tamp >= N) {
			result = half;
			console.log(result)
			min = half + 1;
		} else {
			max = half - 1;
		}
	};
  
  console.log(result);
}

cut(lines, N);

 

 

 

시도해볼만한 예제 2

 

랜선개수 = 5

const 랜선 = [1000, 1200, 800, 1500, 900]

N = 20

 

결괏값 = 245가 나와야 한다.