[JAVA] 프로그래머스 타겟 넘버_탐색

 

문제 : 

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

프로그래머스

 

 

접근 : 

 

  - 입력 받은 수를 모두 합한다.

 

  - 입력 받은 수의 2배 만큼 빼면서 target 과 일치하면 count를 증가 시킨다.

 

  - dfs 를 사용하여 만약 다음 수를 뺄때 target 보다 작으면 더 진행하지 않고 지나간다.

 

  - 수 를 선택하는 방법은 중복 없이 오름차순으로 뽑는다.

     

  - 끝까지 탐색을 진행한 후 결과를 출력한다.

 

 

 

 

 - 코드 구현 : 

class Solution {
    private int[] dou_nums;
    private boolean[] visited;
    private int ans;

    private void dfs(int now, int temp, int target){
        if(temp == target) ans++;

        for(int i = now ; i < dou_nums.length ; i++){
            if(visited[i]) continue;
             if(temp - dou_nums[i] < target) continue;

            visited[i] = true;
            dfs(i + 1, temp - dou_nums[i], target);
            visited[i] = false;
        }
    }
    
    public int solution(int[] numbers, int target) {
        int sum = 0;
        dou_nums = new int[numbers.length];
        visited = new boolean[numbers.length];

        for(int i = 0 ; i < numbers.length ; i++) {
            sum += numbers[i];
            dou_nums[i] = 2 * numbers[i];
        }
        dfs(0, sum, target);
        return ans;
    }
}