[프로그래머스 알고리즘 고득점 Kit][깊이/너비 우선 탐색(DFS/BFS)][Java] 타겟 넘버

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

프로그래머스

프로그래머스 타겟 넘버 풀이

이 문제는 각 숫자 앞에 + 또는 -를 붙여서 target 값을 만들 수 있는 경우의 수를 구하는 문제다.

각 숫자마다 선택지는 두 가지다.

• 현재 숫자를 더한다.
• 현재 숫자를 뺀다.

따라서 DFS를 사용해 모든 경우를 탐색한다.
index는 현재 몇 번째 숫자를 보고 있는지 나타내고, sum은 지금까지 계산한 합을 의미한다.

모든 숫자를 다 사용했을 때 sum == target이면 정답 개수를 1 증가시킨다.

즉, 이 문제는 + / - 선택을 끝까지 탐색하는 DFS 완전탐색 문제다.

 

정답 코드

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