[프로그래머스] 타겟 넘버 Lv2 JAVA [DFS][엄탱]

문제 링크

프로그래머스

문제 설명

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

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

 

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해 주세요.

해설

해당 문제는 DFS문제로 풀 수 있다. 

위에 예시로 한번 생각해 보자.

1. 처음에 올 수 있는 숫자가 +1, -1이 올 수 있고 +1을 선택했다고 가정하자

2. 그다음에는 역시나 +1, -1이 올 수 있다.

3. 이렇게 모든 경우의 수를 정말탐색하여 target이 되는 값을 찾아 나서면 된다.

 

그렇다면 당연히 너비 탐색이 아닌 깊이 탐색을 해나가면서 찾아 나서야 해당 라인이 target이 되는지 알 수 있다.

 

 

예시1

 

위에서 아래 방향이 깊이 탐색이고, 왼쪽에서 오른쪽으로 탐색하는 게 너비 탐색이다.

그림을 보면 깊이 탐색을 해나가면서 찾아 나서야 된다는 것을 알 수 있을 것이다. 

코드

class Solution {
    int answer = 0;
    public int solution(int[] numbers, int target) {
        dfs(0, 0, numbers, target);
        
        return answer;
    }
    
    private void dfs(int sum, int idx, int[] numbers, int target) {
        if (idx == numbers.length && sum == target) {
            answer++;
            return;
        }
        
        if (idx >= numbers.length) {
            return;
        }
        
        dfs(sum + numbers[idx], idx + 1, numbers, target);
        dfs(sum - numbers[idx], idx + 1, numbers, target);
    }
}