[Programmers] 타겟 넘버

사용 언어 : javascript 

lv.2

문제 풀이 소요 시간 : NaN

타입 : DFS/BFS

 

#문제

출처 : 프로그래머스

 

#제출 코드

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

    dfs(0,0)

    function dfs(sum,index){
        if(index === numbers.length){
            if(sum === target){
                answer += 1;
            }
            return;
        }
        dfs(sum + numbers[index], index + 1);
        dfs(sum - numbers[index], index + 1);
    }
    return answer;

}

 

 

재귀 함수를 이용해 DFS로 문제를 푸는 방법. DFS의 구현 방법을 잘 몰라서 하나씩 구현하려다가 시간이 너무 소요되서 결국 힌트를 보았다. 재귀함수를 이용해서 각 index 값들을 더하고 빼고를 반복하는 것이었다.

처음엔 배열의 각 값마다 "-"를 해줘서 넣어주면 되지 않을까? 했었다. (하지만 이건 아주 잘못된 접근법이었고..ㅠㅠ)

예시를 다시 보니 "-"를 한번만 해주는게 아니라 최대 numbers의 개수만큼 넣어보면서 target의 값을 찾는 것이었다. 이미 잘못된 접근으로 인해 25분을 날려먹은 상태였고.. 조급한 마음에 dfs를 어떻게든 구현해보려고 하니 잘 안됐었다. 삼중 반복문이 나오기도 하고.. dfs인지 bfs인지 모를 코드가 나오기도 했었다. 

dfs 개념과 bfs 개념을 자꾸 헷갈리는 것 같은데.. 다시 한번 정리해봐야겠다.