타겟 넘버

문제정의

---

자연수 배열이 주어지고, 이 수들을 적절히 더하거나 빼서 타겟 넘버를 만들 수 있는 경우의 수를 구하는 문제이다.

문제풀이

---

전체 코드는 다음과 같다.

package level2;

public class TargetNumber {

    //프로그래머스 문제풀이 level2 타겟 넘버
    
    public static void main(String[] args) {
        int[] numbers = {1,1,1,1,1};
        int target = 3;
        int answer = 0;
        answer = ReturnAnswer(numbers, 0, target, 0);
        System.out.println(answer);
    }
    public static int ReturnAnswer(int[] numbers, int n, int target, int idx)
    {
        if(n == target && idx == numbers.length)
            return 1;
        else
        {
            if(idx == numbers.length)
                return 0;
            else
            {
                int plus = 0, minus = 0;
                plus += ReturnAnswer(numbers, n+numbers[idx], target, idx+1);
                minus += ReturnAnswer(numbers, n-numbers[idx], target, idx+1);
                return plus+minus;
            }
        }
    }
    
}

이 문제가 왜 dfs인지 한참 고민했는데, 생각해보니 분기를 두개로 나누어가면서 탐색해 나가는 것으로 생각할 수 있다는 결론이 났다. 이를 리컬시브를 통해 구현하였다. 만약 배열의 끝에 도달했을 때 n이 타겟 넘버라면 1을 반환한다. 만약 끝에 도달해도 타겟 넘버를 만들지 못했다면 0을 반환한다. 아직 배열의 끝에 도달하지 않은 경우면 현재 있는 인덱스의 숫자를 더하거나 빼는 두 개의 분기를 만들어 이 둘의 합을 반환한다.

이 문제의 시간복잡도는 $O(2^n)$이다.

테스트