[프로그래머스 43165] 타겟 넘버 (Javascript)

👩🏻‍💻문제링크

[프로그래머스 43165] 타겟 넘버 (Javascript)

✍️Idea Sketch

2021-07-13

1. 문제 이해

• 더하기 빼기 두가지 연산

2. 로직

• DFS
• numbers의 원소를 더하는 경우 or 빼는 경우

3. DFS

• 종료조건 : v === numbers.length 인 경우

sum += numbers[v];  // v번째 원소를 더하는 경우
DFS(v+1);
sum -= numbers[v]*2;  // v번째 원소룰 빼는 경우
DFS(v+1);
sum += numbers[v];  // 원복

✍️소스코드

2021-07-13 정확성 통과

function solution(numbers, target) {
  let cnt = 0;
  let sum = 0;

  function DFS(v) {
    if (v === numbers.length) {
      if (sum === target) cnt++;
      return;
    }
    sum += numbers[v];
    DFS(v+1);
    sum -= numbers[v]*2;
    DFS(v+1);
    sum += numbers[v];
  }
  DFS(0);
  return cnt;
}

✍️명답

DFS getAnswer() 함수의 매개변수에 sum을 포함하는 것이 더 직관적

function solution(numbers, target) {
    let answer = 0;
    getAnswer(0,0);
    function getAnswer(x, value) {  // sum 대신 value 사용
        if(x<numbers.length){
            getAnswer(x+1,value + numbers[x]);
            getAnswer(x+1,value - numbers[x]);
        } else{
            if(value === target){
                answer++
            }
        }
    }
    return answer;
}