[프로그래머스] 타겟 넘버 - 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 이하인 자연수입니다.

입출력 예

numberstargetreturn

[1, 1, 1, 1, 1]	3	5
[4, 1, 2, 1]	4	2

 

분석 및 문제 해결 :

타겟 넘버 문제를 풀기 위해선 나름의 규칙을 이해해야한다.
-1+1+1+1+1 = 3 -----> 1
+1-1+1+1+1 = 3 -----> 2
+1+1-1+1+1 = 3 -----> 3
+1+1+1-1+1 = 3 -----> 4
+1+1+1+1-1 = 3 -----> 5

지금 보는바와 같이 여기에서의 규칙은 -1을 통한 계산을 한다.
타켓과 값이 같은경우를 카운팅을 해야하는것이다.
처음에 생각할때에는 해당 정수 길이만큼 마이너스를 해당 인덱스를 방문했을때의 방문한경우는 true처리하여
다음 인덱스에서 마이너스 연산을 해야하나 싶었다.
오류가 나서 강의를 보고 나서 재정리한다.

일단 우리가 먼저 해야하는것은 정수 배열의 값을 적절히 더하고 뺄때의 타겟과 값이 동일한지를 1 or 0 으로 체크를 하여
타겟과 같으면 1의 값을 더하는 로직을 짜야하는것이다.

느낌상 삽질 느낌이 많이 강했지만 문제 조건에서 결국에는 자기 자신들이 반복되는 규칙을
찾아볼수가 있다. 재귀함수로 돌리면서 + 인경우의 값 - 인경우의 값을 계속 더해서 그값을 다합쳐버리자.

int[] numbers = {
1,1,1,1,1
};
int target = 3;
int res = allTarget(numbers,target,0,0);
System.out.println(res);
}

static int allTarget(int[] numbers, int target, int index,int sum) {
    if( numbers.length == index ) {
        if( sum == target ) {
            return 1;
        }
        return 0;
    }
    return allTarget(numbers,target,index + 1, sum + 1) +
            allTarget(numbers,target,index + 1, sum - 1);
}