53.동전교환 - DFS
Updated:
🔍 문제
다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가?
각 단위의 동전은 무한정 쓸 수 있다
🔹 입력설명
첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다.
두 번째 줄에는 N개의 동전의 종류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다.
각 동전의 종류는 100원을 넘지 않는다
🔹 출력 설명
첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다
🔹 입력예제 1
3
1 2 5
15
🔹 출력 예제 1
3
📌 풀이
<head>
<meta charset="UTF-8">
<title>출력결과</title>
</head>
<body>
<script>
function solution(m, arr) {
let answer = Number.MAX_SAFE_INTEGER;
let n = arr.length;
function DFS(l, sum) {
if (sum > m)
return; // 무한으로 도는것을 방지 하기위해서 왜냐면 sum === m 을 건너 뛰어서 조건이 안맞을때, 계속 for loop 가 돌 수 있기 때문에 sum 이 m 보다 크게 될 경우에 break 를 걸어줘야 함
if (l >= answer) return; // 경우에 수를 줄이는것 l 보다 answer 가 크거나 같게 되면 실행되지 않고 if 문 빠져나가는것
if (sum === m) {
answer = Math.min(answer, l)
} else {
for (let i = 0; i < n; i++) {
DFS(l + 1, sum + arr[i]);
}
}
}
DFS(0, 0);
return answer;
}
let arr = [1, 2, 5];
console.log(solution(15, arr));
</script>
</body>
Leave a comment