[Programmers / Level2] 43165. 타겟 넘버(Java)

💡 Info

• 난이도: Lv2
  프로그래머스 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43165
  풀이 링크(GitHub): hayannn/CodingTest_Java/프로그래머스/2/43165.타겟 넘버

입출력 조건

입출력 예시

문제 이해

• 주어지는 배열과 타겟 넘버를 비교해, 더하기와 빼기 연산으로 타겟 넘버가 되는 경우의 수 구하기

💭 알고리즘

풀이 시간 : 45분

1. 방법의 수를 세는 count 선언

2. DFS 실행하기(numbers, target, index, sum)

3. count 리턴하기

4. 별도 메서드 : DFS

• 현재의 인덱스가 numbers 배열의 끝까지 도달한 경우
  • sum이 타겟 넘버와 일치한다면 -> count++;

import java.util.*;

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

💭 결과