프로그래머스 스쿨(Java - Lv.2) - 타겟넘버 [DFS 단순화]

문제

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

 

해답

class Solution {
    public int sum = 0;
    public int answer = 0;
    public int end;
    public int[] numbers;
    public int target;
    public int solution(int[] numbers, int target) {
        end = numbers.length;
        this.numbers = numbers;
        this.target = target;
        dfs(0);
        return answer;
    }
    
    public void dfs(int i){
        
        if(i>=end) return;
        
        sum+= numbers[i];
        if(i==end-1 && sum==target) answer++;
        dfs(i+1);
        sum-= numbers[i]*2;
        if(i==end-1 && sum==target) answer++;
        dfs(i+1);
        sum+= numbers[i];
        return;
    }
}

 

 

해설

 

DFS를 통해 풀어나가는것이 편한 문제였다.

 

모두 합으로 한뒤 끄트머리에서 다시 재귀로 호출하여

 

더하는경우와 빼는경우를 반복적으로 처리하여 푸는 문제라고 생각하여

 

재귀문법을 사용하여 처리했다.

 

거기에 this를 사용하여 받은 인자를 쉽게 전역으로 넘겨 처리했다.

 

다만 this는 class내의 전역으로 쓰이는 것을 뜻하기에 this를 대입하려다가 에러를 겪었다. 이를 혼동하지말자.