[프로그래머스] 타겟 넘버

 

 

---

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

 

 

개념

DFS

 

 

실행 결과

 

 

 

 

구현 코드(JavaScript)

function solution(numbers, target) {
  function dfs(index, sum) {
    // 다 돌았을 때 합이 target과 같으면 1, 아니면 0을 반환
    if (index === numbers.length) {
      return sum === target ? 1 : 0;
    }
    
    const plus = dfs(index + 1, sum + numbers[index]);
    const minus = dfs(index + 1, sum - numbers[index]);

    return plus + minus;
  }

  return dfs(0, 0);
}

 

 

 

 

코드 설명

먼저 이 문제는 DFS(깊이 우선 탐색) 알고리즘으로 접근해야 한다.

 

DFS를 사용해야 하는 이유?

numbers 내 모든 원소에 대해 +와 -를 적용하고

반복문을 돌면서 이 두 가지 경우에 대한 모든 합을 구해야 한다.

그리고 반복문을 다 돌았을 때 이 합이 target과 일치하면 일치한 횟수를 리턴한다.

여기서 모든 경우를 더하기 위해 재귀를 사용하여 탐색하는 것이다.

 

plus를 사용해 +, minus를 사용해 각각 dfs를 진행한다.

만약 합이 타겟 넘버와 일치하면 일치하는 만큼 각 변수의 값이 +1된다.

재귀를 돌아 타켓넘버와 일치하는 합이 나올때마다 자동으로 값을 더해주기 때문에 

따로 카운트용 변수를 정의하지 않아도 코드가 잘 돌아간다.

 

 

 

---