Programmers 타겟넘버

오랜만에 프로그래머스에서 문제를 풀어보았다. 리트코드처럼 문제풀이가 편리한데 한글로 되어있어 접근성이 좋다.

요즘 능력향상을 위해 노력중인 DFS 문제 중 가장 쉬운 문제를 한 번 풀어보았다.

중심 아이디어

1. 각 numbers 배열의 숫자를 하나씩 방문한다.
2. +혹은 -를 하는 재귀함수가 필요하다.
3. numbers 배열의 마지막 인덱스에 도달했을 때 타겟넘버와 같다면 result 값을 1증가 시킨다.

제출한 코드

class Solution {    
    static int answer;
    static int T;
    public int solution(int[] numbers, int target) {
        answer = 0;
        T = target;
        
        int sum = 0;
        
        dfs(numbers, 0,  sum); // 첫번째 숫자로  dfs 탐색을 보낸다.
        
        return answer;
    }
    
    public static void dfs(int[] numbers, int i, int sum){
        if( i < numbers.length ){
            // -로 가는거
            dfs(numbers, i+1, sum+numbers[i]);
            // +로 가는거
            dfs(numbers, i+1, sum-numbers[i]);
        }else if(sum == T){
                answer++;
        }
        return;
    }
}

풀이 후

한동안 그래프 관련 문제들을 많이 접할 예정