IF - 바둑이 승차

문제

철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태
울수가 없다. 철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다.
N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운
무게를 구하는 프로그램을 작성하세요.

예시

Input1	Input2	Output
[81, 58, 42, 33, 61]	259	242

풀이 및 회고

• DFS 를 사용하지 않으면 오히려 더 쉽게 풀리는 문제라, 두 가지 방법으로 풀어봤다.

코드 (DFS)

const solution = (limit, doggiees) => {
	let answer;
	const check = new Array(doggiees.length);
	check.fill(1);
	const answerList = [];
	const DFS = (depth) => {
		if (depth === doggiees.length + 1) {
			let sum = 0;
			for (let i = 0; i < check.length; i++) {
				if (check[i] && sum + doggiees[i] <= limit) sum += doggiees[i];
			}
			answerList.push(sum);
		} else {
			check[depth] = 1;
			DFS(depth + 1);
			check[depth] = 0;
			DFS(depth + 1);
		}
	};

	DFS(0);
	answer = Math.max(...answerList);
	return answer;
};

코드 (Non-DFS)

const solution = (limit, doggies) => {
	doggies.sort((a, b) => a - b);

	while (true) {
		const sum = doggies.reduce((acc, cur) => acc + cur, 0);
		if (sum > limit) doggies.shift();
		else {
			return sum;
		}
	}
};
};