[Level 2] [Java] 타겟 넘버

문제

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼면 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1 +1 +1 +1 +1 = 3 +1 -1 +1 +1 +1 = 3 +1 +1 -1 +1 +1 = 3 +1 +1 +1 -1 +1 = 3 +1 +1 +1 +1 -1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

• 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
• 각 숫자는 1 이상 50 이하인 자연수입니다.
• 타겟 넘버는 1 이상 1000 이하인 자연수입니다.

 

입출력 예

numbers	target	return
[1, 1, 1, 1, 1]	3	5

 

문제 풀이

dfs 탐색 기법의 재귀 원리를 이해한다면 어렵게 구현되지 않을 것입니다. 다만 재귀를 구현해야한다는 점이 저에게도 아직 어렵게 느껴지는 문제입니다. 재귀의 원리를 이해하고 싶으면 상태공간 트리를 직접 그려보는 방법이 많이 도움이 됩니다.

 

Java Code

package com.programmers.java;


public class Solution {
    static int awer;
    
    public static void main(String[] args) {
        Solution s = new Solution();
        
        int[] numbers = {1, 1, 1};
        int target = 2;
        
        s.solution(numbers, target);
    
    }
  
    public int solution(int[] numbers, int target) {
        dfs(numbers, target, 0);
        
        return answer;
    }

    private void dfs(int[] numbers, int target, int index) {
        if (index == numbers.length) {
            int sum = 0;
            
            for (int num : numbers) sum += num;
            
            if (sum == target)
                answer++;
            
            return;
        }
        
        numbers[index] *= 1;
        dfs(numbers, target, index + 1);
        
        numbers[index] *= -1;
        dfs(numbers, target, index + 1);
        
    }

}