프로그래머스 - 타겟 넘버

타겟 넘버

https://programmers.co.kr/learn/courses/30/lessons/43165?language=javascript

 

※ 문제 설명은 위 링크 참고

문제 풀이

permutation 과 dfs 그 어딘가에 있는 문제 같다. 주어진 numbers 의 길이 만큼만 + , - 연산을 계속 진행하면 된다.

 

핵심 dfs 함수는 인자로는 cur, count 두 개를 받고 다음과 같은 의미를 가진다.

• cur : + , - 연산으로 지금까지 계산한 값
• count : 현재까지 사용한 numbers 내의 숫자 개수

function dfs(cur, count) {
        // numbers 의 length 만큼 탐색했다면 현재까지 계산 된 값이 target 과 일치하는지 확인한다.
        if(count == length) {
              if(cur === target) {
                  answer++;
              }     
            return;
        }

        // 현재 계산 된 값 + 다음 숫자
        dfs(cur+numbers[count], count+1);
        // 현재 계산 된 값 - 다음 숫자
        dfs(cur-numbers[count], count+1);
 }

 

[1,2,3,4,5] 가 들어왔다면

+1 -> +1+2 -> +1+2+3 ...

     -> +1-2  -> +1-2+3 ...

-1 -> -1+2 -> -1+2+3 

    -> -1-2 -> -1-2 +3 ...

 

위와 같이 가지치기 처럼 진행된다. 

 

전체 코드

function solution(numbers, target) {
    var answer = 0;
    const length = numbers.length;

    function dfs(cur, count) {
        if(count == length) {
              if(cur === target) {
                  answer++;
              }     
            return;
        }

        dfs(cur+numbers[count], count+1);
        dfs(cur-numbers[count], count+1);
    }
    // 초기값 0 부터 시작한다.
    dfs(0,0);
    return answer;
}