[Programmers] #43165 - 타겟 넘버 [Java][C++][Python]

문제 링크

---

1. 아이디어

각 수 앞에 + 또는 -를 붙이는 모든 조합을 시도해, 마지막 수까지 부호를 정했을 때 합이 target과 같은 경우의 수를 센다. 수의 개수가 최대 20개라 조합은 $2^{20}$ 정도이고 완전 탐색으로 충분하다.

BFS는 큐에 부분합을 담고, 수 하나를 처리할 때마다 현재 큐에 있던 각 부분합을 꺼내 +x, -x 두 값을 다시 넣는다. 모든 수를 처리한 뒤 큐에 남은 값 중 target과 같은 것의 개수가 답이다.

DFS는 현재 합과 처리한 수의 개수를 인자로 재귀를 돌며, 개수가 전체 길이에 도달하면 합이 target인지에 따라 0 또는 1을 반환하고, 그렇지 않으면 +와 - 두 갈래의 결과를 더한다.

---

2. 복잡도

접근	시간	공간
BFS	$O(2^N)$	$O(2^N)$
DFS	$O(2^N)$	$O(N)$

($N$ = numbers의 길이. BFS는 마지막 단계에서 큐가 부분합 $2^N$개를 담고, DFS는 재귀 깊이만큼만 스택을 쓴다)

---

3. 코드

풀이: BFS [Java][C++][Python]

import java.util.*;

class Solution {
    public int solution(int[] numbers, int target) {
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(0);

        for (int x : numbers) {
            int sz = q.size();
            while (sz-- > 0) {
                int cur = q.poll();
                q.offer(cur + x);
                q.offer(cur - x);
            }
        }

        int cnt = 0;
        while (!q.isEmpty()) {
            if (q.poll() == target) cnt++;
        }

        return cnt;
    }
}

#include <bits/stdc++.h>
using namespace std;

int solution(vector<int> numbers, int target) {
    queue<int> q;
    q.push(0);

    for (int x : numbers) {
        int sz = q.size();
        while (sz--) {
            int cur = q.front();
            q.pop();

            q.push(cur + x);
            q.push(cur - x);
        }
    }

    int cnt = 0;
    while (!q.empty()) {
        if (q.front() == target) cnt++;
        q.pop();
    }

    return cnt;
}

from collections import deque


def solution(numbers, target):
    q = deque([0])

    for x in numbers:
        for _ in range(len(q)):
            cur = q.popleft()
            q.append(cur + x)
            q.append(cur - x)

    return q.count(target)

---

풀이 2: DFS [Java][C++][Python]

class Solution {
    public int solution(int[] numbers, int target) {
        return dfs(0, 0, numbers, target);
    }

    static int dfs(int cur, int depth, int[] numbers, int target) {
        if (depth == numbers.length) return cur == target ? 1 : 0;

        return dfs(cur + numbers[depth], depth + 1, numbers, target) +
                dfs(cur - numbers[depth], depth + 1, numbers, target);
    }
}

#include <bits/stdc++.h>
using namespace std;

int dfs(int cur, int depth, vector<int>& numbers, int target) {
    if (depth == numbers.size()) return cur == target;

    return dfs(cur + numbers[depth], depth + 1, numbers, target) +
           dfs(cur - numbers[depth], depth + 1, numbers, target);
}

int solution(vector<int> numbers, int target) {
    return dfs(0, 0, numbers, target);
}

import sys

sys.setrecursionlimit(10**6)


def solution(numbers, target):
    n = len(numbers)

    def dfs(cur, depth):
        if depth == n:
            return int(cur == target)
        return dfs(cur + numbers[depth], depth + 1) + dfs(cur - numbers[depth], depth + 1)

    return dfs(0, 0)

---