(프로그래머 | 자바스크립트) 코딩테스트 Lv2 – 목표수

문제 설명

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

인수, 숫자, 사용 가능한 숫자의 배열 및 목표 숫자가 주어지면 숫자를 적절하게 더하고 빼서 목표 숫자를 만드는 방법의 수를 반환하는 솔루션 함수를 작성하십시오.

한계

○ 주어진 숫자의 수는 2에서 20 사이여야 합니다.

○ 각 비트는 1보다 크거나 같고 50보다 작거나 같은 자연수입니다.

○ 대상 숫자는 1에서 1000 사이의 자연수입니다.

입력 및 출력 예

내 솔루션

function solution(numbers, target) {
    let answer=0;
    let array = Array(numbers.length).fill(0);      // 값을 넣어줄 빈 배열 생성
    function def(n){ 
        if(n===numbers.length){     // 배열의 끝까지 돌았다면 중단
            let hap = array.reduce((a,b)=>a+b);     // 배열의 합을 구한다.


            if(hap===target){           // 합이 target과 같으면 answer++
                answer++;
            }
        }else{                          
            array(n)=numbers(n);            // 값을 그대로 대입
            def(n+1);
            array(n)=(-numbers(n));         // - 부호를 넣어서 대입
            def(n+1);
        }
    }
    def(0);
    return answer;
}

---

DFS/BFS를 사용하면 이 문제가 해결됩니다.

이 알고리즘을 사용해 푸는 것이 처음이라 처음에는 어색했고, 어떻게 풀어야 할지 감이 잡히지 않았습니다.

그래서 하루 동안 DFS/BFS를 확인하고 강의를 듣고 나서 문제를 풀 수 있었습니다.

DFS로 해결했기 때문에 재귀 함수를 사용했습니다.

다른 분들의 풀이를 보다가 재귀함수가 매개변수 두 개로 풀린 것을 보고 풀이를 바꾸고 싶어서 이렇게 풀었습니다.