[프로그래머스,Level 2] 타겟 넘버 (JAVA 구현)

- 첫 풀이 및 정답풀이

  DFS, BFS를 이용한 완전 탐색 문제를 풀 때는 항상 무엇을 탐색의 대상으로 삼아야 하는지에 대한 기준을 내리지 못해 삽질을 많이 하는 것 같다. 문제에 대한 이해는 간단했다. 완전탐색을 이용해 모든 경우의 수를 고려하면 된다. 

  

  예를 들어, 예제의 경우 1이 5가지가 있다. 이것을 이용해 만들 수 있는 경우의 수는 +1+1+1+1+1 / +1+1+1+1-1 / +1+1+1-1+1/ +1+1+1-1-1........ 등과 같이 다양하게 존재한다. 모든 숫자에 대한 탐색이 끝났을 때, 해당 식의 값이 target값과 동일하다면 카운팅 해주면 된다.

 

  본인은 위의 내용을 모두 생각한 뒤 반복문을 이용해 짜보려고 하였지만 결국 삽질이었다. 결국 적절한 변수 하나만을 이용하면 간단하게 풀 수 있는 문제였다.

 

class Solution {
    static int answer;
    
    // 3. dfs(numbers, target, idx:몇 번째 인덱스인지, sum: idx까지 누적된 값).
    public void dfs(int[] numbers,int target,int idx,int sum){
        // 4. 모든 정수를 탐색했을 때,
        if(idx == numbers.length){   
            // 5. 누적합이 target과 동일하면 answer++ 후 메소드 종료.
            if(sum == target) answer++;
            return;
        }
        
        // 6. 현재 인덱스의 정수를 +로 합해준다.
        sum+=numbers[idx];
        // 7. 다음 인덱스 dfs 수행.
        dfs(numbers,target,idx+1,sum);
        // 8. 6.의 값을 다시 빼준 뒤,
        sum-=numbers[idx];
        // 9. 현재 인덱스의 정수를 -로 합해준다.
        sum+=(-1 * numbers[idx]);
        // 10. 다시 다음 인덱스 dfs 수행.
        dfs(numbers,target,idx+1,sum);
        
    }
    
    public int solution(int[] numbers, int target) {
        // 1. answer은 전역변수로 선언.
        answer = 0;
        
        // 2. dfs수행.
        dfs(numbers,target,0,0);
        
        return answer;
    }
}