99클럽 코테 스터디 34일차 TIL , 타겟 넘버

문제

풀이

입력으로 주어지는 numbers를 +,- 해서 target의 수로 만들 수 있는 경우의 수를 출력하면 된다.

제출 1 - 정답

class Solution {
    private int answer = 0;
    public int solution(int[] numbers, int target) {
        visited = new boolean[numbers.length];
        dfs(numbers, target, 0, 0);

        return answer;
    }
    private void dfs(int[] numbers, int target, int val, int depth){
        if(depth == numbers.length){
            if(target == val) answer++;
            return;
        }
        dfs(numbers, target, val + numbers[depth], depth + 1);
        dfs(numbers, target, val - numbers[depth], depth + 1);
    }
}

 

간단한 dfs문제였다.

각 인덱스마다 부호만 정해주고 depth 닿았을 때 값이 target이면  answer에 1을 더해주면 된다.

TIL

• DFS