타겟 넘버 (JAVA)

문제 설명

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1,1,1,1,1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 리턴하는 함수를 구현하시오.

제한사항

1. 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
2. 각 숫자는 1 이상 50 이하인 자연수입니다.
3. 타겟 넘버는 1이상 1000 이하인 자연수입니다.

풀이

처음 이 문제를 접했을 때는 확률과 통계의 조합처럼 n개 중에서 1개를 뽑을 때, 2개를 뽑을 때 등의 경우의 수를 쭉 나열해서 풀어야하나 생각을 했었습니다. 하지만 이를 구현하려면 아마도 엄청난 경우의 수가 나올것이고 많은 예외가 생길 것임이 분명했습니다.

이 문제에서는 DFS를 사용하면 모든 배열의 수를 효과적으로 탐색할 수 있다고 합니다.

그렇다면 DFS란 무엇일까요?
DFS란 깊이 우선 탐색으로 루트 노드에서 시작해서 다음 분기로 넘어가기전 존재하는 모든 노드, 루트들을 탐색하는 방법입니다.

이는 모든 노드를 방문하고자 하는 경우에 사용합니다. 그래서 이 문제에서도 사용합니다.
자세한 내용은 알고리즘을 공부할 때 더 자세히 업로드 하겠습니다.

즉 하나 하나의 인덱스 정수를 더하고, 빼면서 마지막 인덱스까지 탐색이 완료되었을 때 계산된 sum의 결과가 target과 일치한지 확인하고 일치하면 1을 반환해줍니다.
(일치하면 한가지 경우를 찾은 것 이므로 1을 더해주기 위해서)

최종 코드 및 결과

version1

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

    private int DFS(int[]numbers, int index, int sum, int target){
       if(index == numbers.length){
            if(sum == target)
                return 1;
            return 0;
        }
        return DFS(numbers,index+1,sum + numbers[index],target) + DFS(numbers, index+1,sum - numbers[index],target);
    }
}

version2

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

    private static int dfs(int []numbers, int index, int sum, int target){
        if(index == numbers.length){
            if(sum == target){
                return 1;
            }
            return 0;
        }
        return dfs(numbers,index+1,sum+numbers[index],target) + dfs(numbers,index+1,sum-numbers[index],target);
    }  
}

실행결과