Music Video (Decision Tree Algorithm)

Problem

Genie Records is trying to sell the live video of the undisputed singer Youngpil Cho on DVD. A total of N songs are included in a DVD, and when recording on a DVD, the order in live should be maintained. Our singer Youngpil Cho hates the change of order. That is, in order to record songs 1 and 5 on the same DVD, all songs between 1 and 5 must also be recorded on the same DVD. Also, don’t split a song and record it on two DVDs.

From the point of view of Genie Records, we are not sure if this DVD will be sold, so we try to reduce wasted DVDs in this business as much as possible. After much deliberation, Genie Records decided to record all the videos on M DVDs. At this time, the size of the DVD (recordable length) is to be minimized. And since all M DVDs must be of the same size, the manufacturing cost is low, so they must be exactly the same size.

input

• In the first line, natural numbers N(1≤N≤1,000) and M(1≤M≤N) are given
• On the next line, the length of the songs sung in the order that Youngpil Cho sang them live in minutes (a natural number) is given
• Assume that the length of the sung song is not more than 10,000 minutes

9 3

1 2 3 4 5 6 7 8 9

output

• From the first line, print the minimum capacity size of the DVD

17;

// Description: If the capacity of 3 DVDs is 17 minutes, (1, 2, 3, 4, 5) (6, 7), (8, 9) can be recorded on 3 DVDs. You cannot record all the videos on 3 DVDs with a capacity smaller than 17 minutes.

Solution

Desision Algorithm

function count(songs, capacity) {
	let cnt = 1,
		sum = 0;

	for (let x of songs) {
		if (sum + x > capacity) {
			cnt++;
			sum = x;
		} else sum += x;
	}
	return cnt;
}

function solution(m, songs) {
	let answer,
		lt = Math.max(...songs),
		rt = songs.reduce((a, b) => a + b, 0);

	while (lt <= rt) {
		let mid = parseInt((lt + rt) / 2);

		if (count(songs, mid) <= m) {
			answer = mid;
			rt = mid - 1;
		} else lt = mid + 1;
	}

	return answer;
}

using recursive while loop

function solution(m, songs) {
	let answer,
		rt = songs.reduce((a, b) => a + b, 0),
		expected = Math.floor(rt / m),
		sum = 0,
		cnt = 1,
		i = 0;

	while (i < songs.length) {
		if (sum + songs[i] > expected) {
			sum = 0;
			cnt++;
		}
		sum += songs[i++];

		if (cnt > 3) {
			expected++;
			i = 0;
			cnt = 1;
			sum = 0;
		}
	}

	answer = expected;

	return answer;
}