99클럽 코테 스터디 9일차 TIL, DFS,BFS(타겟 넘버)

1. 문제 정의

 

2. 문제 접근

 

dfs를 통해 더하는 것과 빼는 것의 모든 경우를 구하면 될  것 같다.

3. 문제 풀이

1. dfs를 통해 모든 경우를 다 구한다.
2. target 이랑 값을 비교해 본다.

4. 코드

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

            dfs(numbers, depth+1, target, plus);
            dfs(numbers, depth+1, target, minus);
            
        }
    }
}

5. 회고

저번 시간에 이어 똑같이 dfs 관련 문제였다. 단순히 2가지 경우에 대하여 모든 경우를 구해주면 된다.