[프로그래머스/JAVA] 타겟 넘버

 

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

프로그래머스

---

- 문제 풀이

• 이 함수는 재귀적으로 모든 경우의 수를 탐색합니다.
• 매 단계마다 현재 숫자를 더하거나 빼는 두 가지 선택지가 있습니다.

 

 

깊이 우선 탐색(DFS)으로 경우의 수 탐색

private void dfs(int depth, int[] numbers, int target, int sum) {
    // 모든 숫자를 다 사용했을 때 (depth가 numbers의 길이와 같을 때)
    if (depth == numbers.length) {
        // 사용한 숫자들의 합이 target과 같으면 정답 카운트 증가
        if (sum == target) {
            answer++;
        }
        return;
    }

    // 현재 숫자를 더한 경우
    dfs(depth + 1, numbers, target, sum + numbers[depth]);

    // 현재 숫자를 뺀 경우
    dfs(depth + 1, numbers, target, sum - numbers[depth]);
}

 

• 이 함수는 재귀적으로 모든 경우의 수를 탐색합니다.
• 매 단계마다 현재 숫자를 더하거나 빼는 두 가지 선택지가 있습니다.
• depth는 현재 탐색 중인 숫자의 인덱스를 의미합니다.
• 끝까지 탐색한 후(depth == numbers.length), 합이 목표값과 같은지 검사합니다.

 

- 아래와 같이 트리 형태로 전체 탐색 구조

 

---

 

- 정답 코드

import java.util.*;

class Solution {
    int answer = 0;

    private void dfs(int depth, int[] numbers, int target, int sum) {
        // 모든 숫자를 다 사용했을 때 (depth == numbers 배열의 길이)
        if (depth == numbers.length) {
            if (sum == target) {
                answer++;
            }
            return;
        }

        // dfs(0, [1, 1, 1, 1, 1], 3, 0) ->초기 상태
        // 현재 숫자를 더한 경우
        dfs(depth + 1, numbers, target, sum + numbers[depth]);
        // dfs(1, [1, 1, 1, 1, 1], 3, 1);

        // 현재 숫자를 뺀 경우
        dfs(depth + 1, numbers, target, sum - numbers[depth]);
        // dfs(1, [1, 1, 1, 1, 1], 3, -1);
    }

    public int solution(int[] numbers, int target) {
        dfs(0, numbers, target, 0);
        return answer;
    }
}