[programmers] Lv.2 타겟 넘버 (java)

✏️ 문제

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

🤖 알고리즘

 

#DFS

 

 

🤯 풀이 방법

 

무조건 끝까지 가야 하기 때문에 DFS를 사용했다.

순서를 바꾸지 않기 때문에 앞에서부터 차례대로 더하고, 빼는 경우만 분기를 나누어서 끝까지 탐색해주면 된다.

재귀를 이용해 다음 인덱스로 나아가며 더하거나 빼주고,

마지막 인덱스에 도달한 경우 타겟 넘버와 같은지 판단하여 정답에 1을 더한다.

 

👾 구현 코드 (자바)

class Solution {
    public static int answer;
    public static void DFS(int idx, int cur, int[] numbers, int target) {
        // 마지막 인덱스에 도달한 경우 타겟 넘버가 되는지 확인
        if (idx == numbers.length) {
            if (cur == target) {
                answer++;
            }
            return;
        }
        
        // 더하는 경우와 빼는 경우 각각 탐색
        DFS(idx + 1, cur - numbers[idx], numbers, target);
        DFS(idx + 1, cur + numbers[idx], numbers, target); 
    }
    
    public int solution(int[] numbers, int target) {
        answer = 0;
        DFS(0, 0, numbers, target);
        
        return answer;
    }
}

 

 

프로그래머스