인프런 커뮤니티 질문&답변
작성한 질문수
동전교환 응용문제 질문
작성
·
268
0
선생님 섹션 8의 9번 동전교환 문제를 복습하면서 풀어보니 손에 익어서 이젠 풀 수 있게 되었습니다.
여기서 문제를 변형시켜서 가장 적은 동전갯수를 반환하는게 아닌, 가장 작은 동전 갯수를 가진 동전 종류의 배열 (해당 문제의 경우 [5,5,5])를 반환하도록 문제를 풀고있는 중인데요.
간단할 거 같았는데 의외로 잘 안풀리네요 ㅠㅠ
출력해보면서 이리저리 해보는데 접근 방법과 풀이를 알려주실 수 있을지 여쭙습니다.
아래는 여태 작성한 제 코드입니다.
let answer = Number.MAX_SAFE_INTEGER
let len = arr.length
let tmp = []
function DFS(L , sum){
if (sum > m) return
if (L > answer) return
if (sum === m) {
answer = Math.min(answer, L)
console.log(answer)
console.log(tmp)
tmp = []
}
else {
for (let i=0; i<len; i++){
DFS(L+1 , sum+arr[i])
if (!tmp.length || tmp.reduce((a,b)=>a+b) <= m) tmp.push(arr[i])
}
}
}
DFS(0, 0)
return answer
}
let arr=[1, 2, 5];
console.log(solution(15, arr));
답변 1
0
김태원
지식공유자
안녕하세요^^ tmp 배열중에서 가장 짧은것을 답으로 하면 됩니다.
let answer = Number.MAX_SAFE_INTEGER
let len = arr.length
let tmp = []
function DFS(L , sum){
if (sum > m) return
if (L > answer) return
if (sum === m) {
console.log(tmp)
answer = Math.min(answer, L)
console.log(answer)
console.log(tmp)
tmp = []
}
else {
for (let i=0; i<len; i++){
tmp.push(arr[i]);
DFS(L+1 , sum+arr[i])
tmp.pop();
}
}
}
DFS(0, 0)
return answer
}
let arr=[1, 2, 5];
console.log(solution(15, arr));