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

[문제]

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

코딩테스트 연습 - 타겟 넘버

[설명]

각 배열의 숫자를 이용해 target 으로 결과값을 만들 수 있는 식의 개수를 구하는 방법으로 숫자들 사이에는 +,- 기호만 사용할 수 있다.

만약 a,b,c,d,e 라는 숫자가 있을 때 식으로 만들 수 있는 모든 경우의 수는 32다. (2의 5제곱)

그림으로 표현하면 대충 이런식으로 sum을 구하게 되며 그 후의 과정은 생략하였다

모든 경우의 수를 구해서 해당 식의 결과가 target과 같다면 1을 반환, 아니면 0을 반환하는 함수를 만들어서 사용하였고 알고리즘은 모든 노드를 방문 할 수 있는 DFS(깊이 우선 탐색) 방법을 사용하였다.

 

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

    public int dfs(int[] numbers, int target, int depth, int sum){
        // 배열의 마지막 숫자까지 계산한 경우
        if(depth == numbers.length){
            if(sum == target)       // 결과값과 target이 같다면 카운트 해야 하므로 1을 반환
                return 1;
            else
                return 0;
        }else{
            // 배열의 특정 숫자와 +,- 한 결과값을 전달하고 그 다음 숫자 차례로 넘어감
            return dfs(numbers,target,depth+1,sum + numbers[depth])
                    + dfs(numbers,target,depth+1,sum - numbers[depth]);
        }
    }
}