타겟 넘버 (DFS/BFS)

 

class Solution {
    
    static boolean check[];
    static int N;
    static int count;

    
    public int solution(int[] numbers, int target) {
        
        N = numbers.length;
        check= new boolean[N];
        
        count =0;
        
        dfs(0, numbers, target);
        
        return count;
    }
    
    
    
    public void dfs(int start, int[] numbers, int target) {

        int result=0;
        
        for(int i =0 ;i <N; i++) {
            if(check[i]) {
                result+=numbers[i];
            }else if(!check[i]) {
                result-=numbers[i];
            }
        }
        
        if(result == target) {
         count++;   
        }
        
        
        for(int i=start; i<N; i++) {
            check[i] = true;
            dfs(i+1, numbers, target);
            check[i]= false;
        }
    }
}

 

이전에 백준에서 풀었던 암호 만들기(백준 1759) 와 비슷해서 수월하게 풀었다.

아래 글을 읽어보면, 위의 코드가 잘 설명 될 것이다.

 

 

https://happy-fun.tistory.com/199

1759 암호 만들기(자바)