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

문제 설명

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 이하인 자연수입니다.

 

 

입출력 예

 

 

문제 요약

주어진 숫자 배열에서 각 숫자를 더하거나 빼서 특정 목표값을 만드는 모든 경우의 수를 구하는 문제입니다. 모든 가능한 조합을 탐색해야 하므로 완전 탐색, 그 중에서도 DFS를 활용하기 가장 좋은 전형적인 문제입니다.

 

해결 방법: 상태 트리(State Tree)와 DFS 활용

이 문제의 핵심은 각 숫자마다 +를 할지, -를 할지 두 가지 선택지가 주어진다는 것입니다. 이를 상태 트리로 생각하고 끝까지 탐색(DFS)해 들어가면 됩니다.

1. 상태 정의: 현재 탐색 중인 배열의 인덱스 와 지금까지 계산된 sum을 추적합니다.
2. 재귀 호출: 각 단계마다 현재 숫자를 더하는 경우(+)와 빼는 경우(-) 두 가지로 나누어 재귀 함수를 호출합니다.
3. 종료 조건 : 인덱스가 배열의 끝(numbers.length)에 도달했을 때, 누적합이 타겟 넘버와 같다면 조건 만족! 경우의 수를 1 증가시킵니다.
4. 시간 복잡도: 각 숫자마다 2개의 분기가 생기므로 O(2^n) 의 시간 복잡도를 가집니다. 주어진 숫자의 최대 개수가 20개이므로, 최악의 경우에도 약 100만 번 2^{20}의 연산만 수행하게 되어 제한 시간 내에 충분히 통과할 수 있습니다.

 

제출 코드

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

    //dfs 재귀 함수 정의 (현재 탐색 깊이, 현재까지의 누적합)
    function dfs(depth, sum) {
        //종료 조건: 배열의 끝까지 모두 탐색한 경우
        if (depth === numbers.length) {
            // 누적합이 타겟 넘버와 같다면 정답 카운트 증가
            if (sum === target) {
                answer++;
            }
            // 함수 종료 (더 이상 뻗어나갈 노드가 없음)
            return;
        }

        // 현재 숫자를 더하는 경우의 가지로 뻗어나감
        dfs(depth + 1, sum + numbers[depth]);
        
        //현재 숫자를 빼는 경우의 가지로 뻗어나감
        dfs(depth + 1, sum - numbers[depth]);
    }

    //초기값 세팅 후 탐색 시작 (인덱스 0, 누적합 0)
    dfs(0, 0);

    return answer;
}