[ 자바 /Java ] 프로그래머스 43165 : 타겟넘버

문제

---

 

---

 

풀이

---

1. 한 경우를 끝까지 탐색한다는 점에서 DFS로 풀이
2. 마지막 자리가 아닌 경우(index != numbers.length)
3. 재귀함수를 통해 부호를 바꿔가며 탐색한다.
4. 마지막 자리일 경우 (index == numbers.length)
5. sum을 초기화하고 해당 인덱스의 수를 더한다.
6. 모두 더한 값 sum이 target 넘버와 같을 경우 cnt++

class Solution {
    private static int cnt = 0;
    public int solution(int[] numbers, int target) {
               
        dfs(0, target, numbers);	// DFS를 이용해 풀이
        int answer = cnt;
        
        return answer;
    }

    public void dfs(int index, int target, int[] numbers){
        
        if(index == numbers.length){	// 주어진 배열의 마지막 자리일 경우
            int sum = 0;				// sum초기화
            for(int i=0; i<numbers.length; i++){
                sum += numbers[i];		// sum에 주어진 배열의 수를 더한다
            }
            if(sum == target){			// 배열을 모두 더한 값이 target과 같은 경우
                cnt++;					// cnt++
            }
        } else {						// 마지막자리가 아닐 경우 재귀함수를 통해 부호를 바꿔가며 탐색
            numbers[index] *= 1;
            dfs(index+1, target, numbers);
            
            numbers[index] *= -1;
            dfs(index+1, target, numbers);
        }
    }
}