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

01 Feb 2025 in Study / Coding Test

• ☑️ 문제
• ☑️ 풀이
  • 문제 분석
  • 접근 방법
  • 풀이

☑️ 문제

프로그래머스 43165

☑️ 풀이

문제 분석

• numbers 배열에서 각 숫자에 + , - 를 붙여 모든 경우의 수를 탐색해야한다.
• 결과적으로 target 이 되는 경우의 수를 구해야 한다.

접근 방법

• 각 숫자마다 + 또는 - 를 붙일 수 있으므로 완전 탐색을 해서 n * n 개의 경우의 수를 확인해야 한다.
• DFS 를 활용할 수 있다.

풀이

//시간: 4.60ms
//메모리: 83.6MB

class Solution {
    static int answer = 0;
    static int target;

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

    public void dfs(int[] numbers, int idx, int sum) {
        if (idx > numbers.length - 1) {
            if (sum == target) {
                answer += 1;
            }
            return;
        }

        dfs(numbers, idx + 1, sum + numbers[idx]);
        dfs(numbers, idx + 1, sum - numbers[idx]);
    }
}

• idx 가 numbers.length - 1 과 같거나 더 커진 경우 sum 과 target 이 일치한 지 확인한다.
• 현재 숫자를 더하는 경우와 현재 숫자를 빼는 경우 두 가지로 dfs 메서드를 재귀적으로 호출한다.