[DFS] 타겟넘버

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

풀이

class Solution {
    int cnt = 0;
    public int solution(int[] numbers, int target) {
        int answer = 0;
        dfs(numbers, target, 0, 0);
        answer = cnt;
        return answer;
    }
    
    public void dfs(int[] numbers, int target, int depth, int result){
        if(depth == numbers.length){
            if(target == result){
                cnt += 1; 
            }
            return ;
        }
        int plus = result + numbers[depth];
        int minus = result - numbers[depth];
        dfs(numbers, target, depth + 1, plus);
        dfs(numbers, target, depth + 1, minus);
        
    }
}

 

 

풀이

dfs로 풀되, 헷갈렸던 부분은 어떤 것을 노드로 만드느냐에 대한 부분이었다.

덧셈 / 뺄셈한 값에 대해 재귀문을 걸어 타겟에 가까워졌는지를 본다.