프로그래머스-타겟넘버

Halo·2025년 7월 27일

DFS

Algorithm

목록 보기

74/85

🔍 Problem

프로그래머스-타겟넘버

📃 Input&Output

🌁 문제 배경

가. 문제 설명
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 함수를 작성해주세요.

제한사항
주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
각 숫자는 1 이상 50 이하인 자연수입니다.
타겟 넘버는 1 이상 1000 이하인 자연수입니다.

나. 접근 방법
idx 값을 증가시켜 +, - 를 각 dfs 함수에 넣어 처리하게 하고, 깊이가 배열의 길이만큼 되었다면, 더 깊게 안들어가게 return하게 하였다. 그리고 만약 해당 상황에서 각 값들의 합이 target이랑 같다면 answer count를 1 증가하였다. 최종적으로 answer count를 반환하였다.

다. 문제 유형
dfs

📒 수도 코드

가. dfs의 파라미터를 정한다.

number : 넘겨줄 배열
idx : 위의 배열에서 현재 참조하고 있는 원소 값의 index
dep : 현재 탐색하고 있는 idx의 깊이, 최대 dep : number.length
sum : 더해진 값

나. dfs 동작 1
만약 현재 dfs, tree의 깊이가 number.length와 같다면 더 이상 탐색을 그만하고 다른 가지로 넘어간다. 그리고 해당 상황에서 만약 더해진 합(sum)이 구하고자하는 target(goal_target)과 같다면 정답 카운트를 1 증가시킨다.

다. dfs 동작 2

각 인덱스 값 별로 합과 차가 더해지는 방식으로 계산되므로, 각 dfs를 두번 실행시켜준다.

💻 Code

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