[프로그래머스] 타겟 넘버

문제

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

프로그래머스

접근 방법 및 풀이

배열의 숫자 전체를 서로 더하거나 뺀 결과가 target의 숫자와 같은 경우의 수

문제의 카테고리가 깊이 또는 넓이 우선 탐색이므로 풀이 방법을 둘중에 하나로 선택

배열의 숫자를 모두 사용 해야지만 target과 비교가 가능하므로 깊이 우선 탐색으로 풀이

 

그래프 탐색시 depth는 배열의 index라 설정

 

재귀 함수의 종료 조건은 그래프 탐색의 depth가 배열의 길이와 같은 경우 (배열의 모든 숫자에 대해서 덧셈과 뺄셈의 준비가 된 경우)

그 때의 배열의 합이 target과 같은 경우 1을 반환 하고 같지 않은 경우 0을 반환

 

그래프 탐색의 조건은 각 숫자를 더하거나 빼기를 해야 하므로 덧셈 뺄셈으로 분기를 설정

분기에 대한 반환 값은 해당 분기 이후에서 배열의 합이 target의 숫자와 같은 경우의 수이므로 두가지 분기의 합을 이전 분기로 반환

public class Q30_43165 {
    public int solution(int[] numbers, int target) {
        int answer = dfs(numbers, target, 0);
        return answer;
    }

    public int dfs(int[] numbers, int target, int depth) {
        if (depth == numbers.length) { // 탐색의 종료 조건
            int sum = sum(numbers);
            if (sum == target) {
                return 1; // 조건에 만족하는 경우 1을 반환
            } else {
                return 0;
            }
        }

        // 현재 index의 수의 뺄셈 분기를 생성
        numbers[depth] = numbers[depth] * -1;
        int result0 = dfs(numbers, target, depth + 1);

        // 현재 index의 수의 덧셈 분기를 생성
        numbers[depth] = numbers[depth] * -1;
        int result1 = dfs(numbers, target, depth + 1);

        // 덧셈과 뺄셈 분기 이후에서 조건에 맞는 경우의 수를 합하여 반환
        return result0 + result1;
    }

    public int sum(int[] numbers) {
        int sum = 0;
        for (int number : numbers) {
            sum += number;
        }
        return sum;
    }
}