[PRGM] 43165.타겟넘버 (Java)

1. 문제 요약

숫자 배열이 주어진다. 순서를 바꾸지 않고 각 숫자 앞에 + 또는 -를 붙여서 합이 target이 되는 경우가 몇 가지인지 구하면 된다.

• 숫자 개수 2~20개, 각 숫자 1~50, target 1~1000

2. 접근 과정

숫자마다 부호가 + 아니면 - 둘 중 하나다.

그래서 "0번째 숫자부터 순서대로 부호를 정해나가는" DFS로 접근했다.

• 종료 조건: depth == numbers.length면 모든 부호를 정했다는 뜻이다. 이때 sum == target이면 경우의 수 하나를 찾은 것이다.
• 선택: 더하거나(sum + numbers[depth]) 빼거나(sum - numbers[depth]), 두 갈래로 재귀 호출한다.

3. 코드

class Solution {

    private int[] numbers;
    private int target;
    private int answer;

    public int solution(int[] numbers, int target) {
        this.numbers = numbers;
        this.target = target;
        this.answer = 0;

        dfs(0, 0);

        return answer;
    }

    private void dfs(int depth, int sum) {
        if (depth == numbers.length) {
            if (sum == target) answer++;
            return;
        }
        dfs(depth + 1, sum + numbers[depth]);   // +
        dfs(depth + 1, sum - numbers[depth]);   // -
    }
}

시간복잡도: O(2^n) — 숫자마다 두 갈래로 갈라지므로 잎 노드가 2^n개다. n=20이면 약 104만으로, 실행해보니 4ms였다.
공간복잡도: O(n) — 재귀 깊이. 최대 20단계

sum이 지역 변수(파라미터)라서 각 재귀 호출이 자기만의 복사본을 갖기 때문에 첫 번째 호출이 아무리 sum을 바꿔도 두 번째 호출에는 영향이 없다.