프로그래머스 -타겟 넘버 (java)

https://programmers.co.kr/learn/courses/30/lessons/43165

코딩테스트 연습 - 타겟 넘버

 

푸는데 엄청 오래 걸린 문제...

bfs나 dfs를 안쓰고 풀어서 정석대로 안푼거 같은데 일단 돌아가니깐....

 

class Solution {
    public int solution(int[] numbers, int target) {
        int answer = 0;
        int[][] tree = new int [numbers.length][((int)Math.pow(2,numbers.length))]; 
        tree[0][0] = -numbers[0];
        tree[0][1] = numbers[0];
        // System.out.println(tree[0].length);
        
        for ( int i = 1; i < numbers.length; i++ ){
            int c = 0;
            for(int j=0; j<Math.pow(2,i); j++){
                int parent = tree[i-1][j];
                tree[i][c] = parent - numbers[i];
                c++;
                tree[i][c] = parent + numbers[i];
                c++;
            }
        }
        
//         for(int i = 0; i<tree.length; i++){
            
//             for(int j=0; j<tree[i].length; j++){
                
//                 System.out.print(tree[i][j]+" ");
//             }
//             System.out.println("");
//         }
        
        for(int i :tree[numbers.length-1]){
            if(i==target) answer++;
        }
        
        return answer;
    }
}

 

원래 풀이는 dfs를 이용해 재귀함수로 

return dfs( n+1) + dfs(n-1) ;

이런식으로 푸는거라고 한다 시간 텀을 두고 나중에 다시 풀어야겠다.