[PGS] 타겟 넘버 - JAVA

💡 문제

💬 입출력 예시

📌 풀이(소스코드)

class Solution {
    
    static int answer = 0;
    
    public int solution(int[] numbers, int target) {
        dfs(numbers, target, 0, numbers.length, 0);
        return answer;
    }
    
    public void dfs(int[] numbers, int target, int depth, int n, int sum) {
        if (depth == n) {
            if (sum == target) {
                answer++;
            }
            return;
        }
        
        dfs(numbers, target, depth + 1, n, sum + numbers[depth]);
        dfs(numbers, target, depth + 1, n, sum - numbers[depth]);
    }
}

📄 해설

접근

• DFS 기본 문제
• 각 숫자를 확인하면서 다음 숫자를 더하는 경우와 빼는 경우로 가지를 펼쳐서 수행하면 된다.
• 모든 숫자를 사용했을 때, 그 시점의 합과 타겟 넘버의 값을 비교하면 된다.
• DFS 에 대한 개념만 잘 잡아놓으면 된다. DFS 의 핵심은 가치 뻗기

과정

• dfs 메소드를 호출
• 현재까지 사용된 숫자의 개수인 depth 가 전체 숫자의 개수인 n 과 같다면, 모든 숫자를 사용한 것이므로 현재까지의 결과인 sum 과 target 의 동등 비교를 수행
• 같으면 answer 의 값 증가. 다르면 그냥 종료
• depth == n 이 아니라면 두개의 dfs 메소드를 재귀호출한다.
  • 하나는 다음 숫자를 더하는 경우
  • 하나는 다음 숫자를 빼는 경우