[프로그래머스] 타겟 넘버 (JAVA)

문제 출처 - Programmers

문제는 여기

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

---

[풀이]

1. 배열의 숫자들을 사용하면서 dfs를 돌려 목표 숫자가 맞는 경우를 찾으면 되는 문제이다.

2. dfs에 종료 조건(배열의 모든 숫자를 사용할 경우)을 작성한다.

3. 2에서 합이 주어진 목푯값과 동일하다면 결과를 1 증가시켜준다.

4. 배열의 숫자를 뺐을 때와 더했을 때를 계산해야 하므로 2가지를 dfs로 재귀가 돌아가도록 구현한다.

[접근]

1. 문제를 보고 dfs로 풀면 되겠다고 생각을 하였다.

2. 모든 숫자를 사용했을 때, 주어진 목표의 수와 같다면 횟수를 증가시켜주면 되겠다고 생각하였다.

3. dfs를 재귀로 구현하여 뺐을 경우와 더했을 경우를 나눠서 구현하면 되겠다고 생각하였다.

[코드]

class Solution {
     static int answer;
    
    public int solution(int[] numbers, int target) {
        answer = 0;
        
        dfs(numbers, target, 0, 0);
        
        return answer;
    }
    
    public void dfs (int[] numbers, int target, int index, int sum) {
        if (index == numbers.length) {   
            if(sum == target)
                answer++;
            return;
        }
        
        // 뺏을 때
        sum += (-1 * numbers[index]);
        dfs(numbers, target , index + 1, sum);
        
        // 더했을 때
        sum += numbers[index] * 2; // 이전에 뺐던거를 더해주기 위해 * 2
        dfs(numbers, target, index + 1, sum);
        
    }
}