50.바둑이 승차 - DFS
Updated:
🔍 문제
철수는 그의 바둑이들을 데리고 시장에 가려고 한다.
그런데 그의 트럭은 C킬로그램 넘게 태울수가 없다.
철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다.
N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요
🔹 입력설명
첫 번째 줄에 자연수 C(1<=C<=100,000,000)와 N(1<=N<=30)이 주어집니다.
둘째 줄부터 N마리 바둑이의 무게가 주어진다
🔹 출력 설명
첫 번째 줄에 가장 무거운 무게를 출력한다.
🔹 입력예제 1
259 5
81
58
42
33
61
🔹 출력 예제 1
242
📌 풀이
<head>
<meta charset="UTF-8" />
<title>출력결과</title>
</head>
<body>
<script>
function solution(c, arr) {
let answer = Number.MIN_SAFE_INTEGER;
let n = arr.length;
function DFS(l, sum) {
if (sum > c) return; // c 트럭의 무게에 sum 을 넘어가서 초과 하면 return 해서 재귀함수 종료 시킴
if (l === n) {
answer = Math.max(answer, sum); // answer 와 sum 의 최대값을 비교해서 answer 로 변환
} else {
DFS(l + 1, sum + arr[l]); // 하나씩 level 증가 할때, 처음 수가 포함될 경우 arr 값을 누적
DFS(l + 1, sum); // 하나씩 증가, 처음 수가 포함되지 않은 경우의 수
}
}
DFS(0, 0);
return answer;
}
let arr = [81, 58, 42, 33, 61];
console.log(solution(259, arr));
</script>
</body>
Leave a comment