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

유형 : DFS / BFS

 

문제 

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 이하인 자연수입니다.

 

풀이

NUMBERS 를 더할지 / 뺄지 모든 케이스에 대한 탐색이 필요하며, 이부분은 DFS로 구현한다.

백트래킹 방식이기 때문에 다른 DFS와 다른 점은 반복문의 수행이다.

DFS 함수의 인자로 현재 index가 필요하고, 현재 index 부터 끝 index까지 DFS를 재귀로 호출하는데,

이때 현재 index가 + 일때에 대해 DFS 를 호출하고나서

다시 현재 index가 - 일때 상태로 돌아가는 방식이다.

 

이는 현재 index가 + 일때와, - 일때를 모두 탐색하기 위함이다.

 

static int dfs(int[] numbers, int[] arr, int start, int depth, int n, int target) {
        int res=0;
        for(int i=start; i< n ; i++){  //반복문 수행
            arr[i] = 1;  //현재 index 값이 1인 경우
            res+=dfs(numbers, arr, i+1, depth+1, n, target);
            arr[i] = -1;  //현재 index 값이 -1인 경우
        }
        res+=check(numbers, arr, n, target); //계산하여 target이 나오는지 확인
        return res;
    }

최종 return 값이 answer 즉, 구해지는 모든 경우의 수가 된다.

 

참고)

다른 문제에서의 DFS 함수 동작은 참고적으로 아래와 같다.

(여기서는 현재 INDEX를 방문한 것인지에 대해 체크하는 visited가 반드시 필요하다)

 

public void dfs (int[][] computers, boolean[] visited, int a, int n){
        visited[a] = true;
        for(int i= 0; i<n; i++){
            if(computers[a][i]==1 && visited[i] == false){
                dfs(computers, visited, i, n);
            }
        }
    }

 

 

코드

 

class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        int[] arr = new int [numbers.length];
        int n = numbers.length;
        
        answer = dfs(numbers, arr, 0,0,n,target);
 
        return answer;
    }
    
    static int dfs(int[] numbers, int[] arr, int start, int depth, int n, int target) {
        int res=0;
        for(int i=start; i< n ; i++){
            arr[i] = 1;
            res+=dfs(numbers, arr, i+1, depth+1, n, target);
            arr[i] = -1;
        }
        res+=check(numbers, arr, n, target);
        return res;
    }
    static int check(int[] numbers, int[] arr, int n, int target){
        int sum = 0;
        for(int i= 0; i<n ; i++){
            sum+=numbers[i]*arr[i];
        }
        if(sum==target){
            return 1;
        }
        else return 0;
    }
}