LV2 28 타겟 넘버

문제 설명

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

 

입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

 

나만의 풀이

  이 문제는 BFS, DFS의 지식이 있어야 풀 수 있다. 기본 적으로 문제를 클릭하기 전 알려주고 있다! 하지만 나는 알고리즘에 대해 전혀 알지 못해 공부를 하고 문제를 풀었다.

  우선 이 문제는 DFS를 필요로 한다. DFS란 간단하게 말하면 경우의 수를 아는 것인데 모든 경우가 아닌 상의 요소와 하위 요소가 이미 정해져 있고 자리를 바꾸지 않는다. DFS는 상위에서 하위까지 수직으로 1개 1개씩 스켄하는 원리라고 알면 된다. (검색하면 바로 나와요~~)

  이 문제는 DFS를 활용하는 가장 기초적인 문제라고 생각이 든다. 왜냐하면 상위에서 하위로 내려갈 때 경우의 수가 숫자 하나에  +, - 만 하면 되기 때문에 두 가지 밖에 없다.

  이 것을 자동으로 해주는 코드만 구성하면 끝이다~~

function solution(numbers, target) {
    let count = 0;
  
    function DFS(index, sum) {
        if (index === numbers.length) { 
            if (sum === target) { 
                count++; 
            }
            return;
        }
    
        DFS(index + 1, sum + numbers[index]); 
        DFS(index + 1, sum - numbers[index]); 
    }
  
    DFS(0, 0);
  
    return count;
}