기타 레슨

문제

백준 2343번 - 기타 레슨

언어

JavaScript

순서도

이진 탐색을 진행할 범위 정하기 (left 값과 right 값 찾기)
이진 탐색을 통해서 조건을 만족하는 가장 작은 블루레이의 크기 구하기

문제 풀이 step 1

기타 레슨 동영상 목록과 블루레이의 개수가 주어질 때, 블루레이의 크기의 최솟값을 구하는 문제입니다.
우선, 이진 탐색을 하기 위해서는 탐색을 진행할 범위를 정해야 합니다.
- 우리가 탐색을 통해서 얻어야 하는 정보는 블루레이의 크기이며, left 와 right 로 블루레이의 크기의 범위를 정하면 되겠습니다.
- left 에는 가능한 블루레이의 크기의 최솟값을 구해야 합니다.
  - 이는 주어진 기타 레슨 동영상 목록 중에서 최댓값을 구하면 됩니다.
  - 최댓값을 구하는 이유는 그렇게 해야 모든 레슨 동영상을 블루레이로 만들 수 있기 때문입니다.
- right 에는 가능한 블루레이의 크기의 최댓값을 구해야 합니다.
  - 이는 모든 기타 레슨 동영상 목록의 값들의 합을 구하면 됩니다.
범위를 정했으니, 이진 탐색을 진행하면 됩니다.
- 매 탐색마다 나오는 mid 값으로 블루레이를 만들어보고, 만든 블루레이의 개수를 셉니다.
- 블루레이의 개수가 m 보다 크다면, 너무 조금씩 블루레이로 만든 것이기 때문에 left 값을 mid + 1 로 갱신합니다.
- 블루레이의 개수가 m 보다 같거나 작다면, 너무 많이씩 블루레이로 만든 것이기 때문에 right 값을 mid - 1 로 갱신합니다. (그리고 min 값을 갱신합니다.)
위 과정을 통해서 찾아낸 min 값을 출력하면 정답입니다.
추가 설명은 주석으로 작성하겠습니다.

후기

오랜만에 이진 탐색 문제를 풀어서, 블로그의 예전의 풀이를 쭉 훑어보고 풀었습니다.
다시 한 번 확인할 수 있었던 것은,
- 이진 탐색 문제에서는 탐색 범위를 정확하게 정해야 한다는 점과
- 이진 탐색은 특정 값을 찾는 상황뿐만 아니라, 가장 조건을 만족하는 최적의 값을 찾는 상황에서도 쓰인다는 점입니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

// mid 값으로 블루레이를 만들어보고, 만든 블루레이의 개수를 구하는 함수
const getCnt = (n, lessons, mid) => {
	let cnt = 0;
	let sum = 0;
	for (let i = 0; i < n; i++) {
		sum += lessons[i];

		if (sum > mid) {
			cnt += 1;
			sum = lessons[i];
		}
	}

	return cnt + 1;
};

const solution = (input) => {
	const [n, m] = input[0].split(" ").map(Number);
	const lessons = input[1].split(" ").map(Number);

	let min = 1;
	// 이진 탐색의 범위 정하기
	let [left, right] = [0, 0];
	for (let i = 0; i < n; i++) {
		left = Math.max(left, lessons[i]);
		right += lessons[i];
	}

	// 이진 탐색
	while (left <= right) {
		let mid = parseInt((left + right) / 2);

		const cnt = getCnt(n, lessons, mid);

		// 블루레이의 개수가 m 보다 큰 경우
		if (m < cnt) {
			left = mid + 1;
		}
		// 블루레이의 개수가 m 보다 같거나 작은 경우
		else {
			min = mid;
			right = mid - 1;
		}
	}

	// 가장 최적의 값 return
	return min;
};

console.log(solution(input));