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

1. 문제 설명

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. 제한사항

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

 

 

3. 입출력 예

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

 

 

4. 문제를 보고 가진 생각 정리

위 문제는 5개수를 모두 사용하여 나올 수 있는 경우의 수를 생각하여야 한다. 위 테스트 케이스 기준 나올 수 있는 총 경우의 수는 2^5로 32개이다. 이 경우의 수를 이진 그래프로 나타내보았다.

 

모든 경우의 수를 표현하려면 그림이 너무 커져서 2개의 수에 대해서만 생각을 해보았다. 문제 예시처럼 5개의 수가 주어진다면, 깊이가 5인 곳에서의 모든 경우의 수에 대한 합을 구하여 target과 일치하는 로직으로 풀이를 하면 될 것이라고 생각하였다. 또한, 깊이 우선으로 탐색을 하여야 하기 때문에, 함수에서 함수를 호출하는 재귀 함수를 선택하기로 하였다. 

 

 

5, 풀이 코드

class Solution {
    
    int answer = 0;
    
    public int solution(int[] numbers, int target) {
    	//4번의 그림에서 start와 같은 로직
        search(numbers, target, 0);
        return answer;
    }
    
    public void search(int[] numbers, int target, int depth){
    
    	//입력된 numbers의 length까지 탐색을 완료하였을 경우, 배열의 합을 구하여 target과 비교
        if(numbers.length == depth){
            int sum=0;
            for(int i=0;i<numbers.length;i++){
                sum+=numbers[i];
            }
            if(sum==target)
                answer++;
        //탐색이 완료되지 않았다면, 다음 depth에 해당하는 탐색을 진행한다.
        //numbers에서 제공된 수가 양수일 수도 있고, 음수일 수도 있기 때문에 두 경우에 대해 탐색 진행.
        }else{
            search(numbers, target, depth+1);
            numbers[depth]*=-1;
            search(numbers, target, depth+1);
        }
    }
}