프로그래머스 타겟 넘버 JavaScript
2023년 1월 17일
문제 풀이
DFS로 푼 문제였다. numbers의 길이가 최대 20개이기에 모든 경우의 수를 다 계산해준다.
numbers가 [4, 1, 2, 1] 이면
[] => [+4, -4] => [+4+1, -4+1, +4-1, -4-1] => [+4+1+2, -4+1+2, +4-1+2, -4-1+2, +4+1-2, -4+1-2, +4-1-2, -4-1-2] => ...
이런 식으로 현재 값에서 계산해 줄 numbers[idx] 값을 +해주는 경우와 -해주는 경우를 모두 탐색한다.
solution.js
function solution(numbers, target) {
let answer = 0;
const dfs = ((num, idx) => {
if (idx === numbers.length-1) {
if (num === target) {
answer++;
}
return;
}
dfs(num+numbers[idx+1], idx+1);
dfs(num-numbers[idx+1], idx+1);
})
dfs(0, -1);
return answer;
}