[프로그래머스]JAVA - Level2. 타겟 넘버

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

프로그래머스

풀이

주어진 숫자들로 덧셈과 뺄셈만을 이용해서 목표값을 만드는 문제이다.

모든 경우의 수를 거쳐야하므로 깊이 우선 탐색 (dfs)가 바로 생각이 났다. dfs 함수를 생성하고 마지막 노드까지 탐색했을 때 목표값과 일치한다면 answer++를 해주는 방식으로 코드를 설계했다.

 

여기서 중요한 건 목표값을 도달했을 때 answer++를 해주는 것이 아닌 마지막 노드까지 탐색을 완료해야한다는 점이다.

깊이 우선 탐색 (dfs)를 잘 모르는 경우 아래를 참고해주면 좋다.

[JAVA] 깊이 우선 탐색 DFS 개념과 작동 방식

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