[프로그래머스] 타겟 넘버 (3가지 풀이 방식, DFS, 트리, 그리고 수학적 공식을 이용한 최적화)
📌 문제
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 이하인 자연수입니다.
입력
| numbers | target | return |
| [1, 1, 1, 1, 1] | 3 | 5 |
| [4, 1, 2, 1] | 4 | 2 |
👀 문제 해석
이 문제는 고정된 순서를 유지한 채 각 원소에 ‘+’ 또는 ‘–’ 기호를 부여하여, 모든 기호 결정이 끝났을 때 누적합이 정확히 target 에 일치하는 경우의 수를 묻는 문제이다.
- 원소의 개수 n 은 최대 20, 각 값은 50 이하이므로, 가능한 기호 조합 수는 2^n ≤ 1,048,576 개에 불과하다.
- 문제는 “몇 가지 방법이 존재하느냐”만 요구하므로, 실제 식을 출력하거나 경로를 저장할 필요는 없다.
- 알고리즘 분류 관점에서 보면
- 상태 공간이 완전하게 결정 트리 형태로 펼쳐질 수 있으므로 Brute-Force/완전 탐색 문제이며,
- DFS·BFS 중 어떤 트리 탐색 기법을 택해도 시간·메모리 제약을 넘지 않는다.
- 다만, 부분 문제(인덱스, 현재 합)로 나누어 “앞으로 남은 수들의 합이 어떻게 되든 target 에 도달할 수 있는가”를 메모이제이션 하면 탑-다운 DP 로도 해석할 수 있어, 전형적인 “부분합 DP + 부호 선택” 문제군에 속한다.
정리하면, 이는 깊이 n 인 이진 결정 트리에서 리프 노드 중 “합 = target” 인 리프의 개수를 세는 문제이며, 탐색 자체가 알고리즘의 전부라고 볼 수 있다.
🔎 접근
“모든 부호 조합을 다 뒤져도 될까?”
“제약이 작으니 완전 탐색이 안전하지 않을까?”
“그래도 혹시 더 우아한 방법은 없을까?”
문제를 풀면서 이런 고민들을 했다. 그리고 스터디에서 스터디에서 이 문제를 함께 토론하며 여러 해법들을 탐구했다.
"모든 부호 조합을 다 뒤져도 될까?"
- 주어진 숫자 배열의 길이는 최대 20이다. 각 숫자마다 '+' 또는 '–'의 두 가지 선택지만 존재하므로 가능한 조합 수는 2^20으로 약 100만 가지 정도이다. 이는 시간 제약 내에 충분히 처리 가능한 수준이다.
- 따라서, 직관적으로는 단순히 모든 경우를 전부 탐색하는 Brute-force 접근(DFS나 BFS)으로도 제한 시간 안에 해결 가능하다는 점이 명확하다.
"제약이 작으니 완전 탐색이 안전하지 않을까?"
- DFS 방식을 선택하여 트리를 깊이 우선으로 완전 탐색하면, 각각의 리프 노드에서 누적합이 target과 일치하는 경우를 세는 방식으로 충분히 구현 가능하다.
- 실제로 본인은 처음 이 문제를 DFS를 통해 접근하여 풀이하였다. 모든 선택을 탐색한 후, 조건에 부합하는 경우만 카운트하여 해결하였다.
"그래도 혹시 더 우아한 방법은 없을까?"
- 완전 탐색은 가능하지만, 좀 더 우아한 접근 방법이 없는지 고민해보게 되었다.
- 스터디 시간에 다른 스터디원이 트리 모델링 관점에서 접근하는 방법을 제시하였다.
- 문제를 곰곰이 생각해보면, 인덱스마다 두 가지(더하기·빼기) 선택지만 존재하고, 이 선택이 인덱스를 따라 연속적으로 이어지면서 하나의 식이 완성된다.
- 이로써 문제 자체는 “깊이 n 레벨의 이진 결정 트리”로 모델링된다. 결정 과정을 그대로 펼치면 깊이 n의 이진 결정 트리가 만들어지고 리프 노드 2ⁿ 개 중 누적합이 타깃과 일치하는 리프의 개수를 구하면 된다.
- 이렇게 보면 결정 트리(decision tree)에서 리프노드의 개수를 세는 문제로 볼 수도 있다.
- 즉, 결정 트리로 상태를 정의하여 체계적인 탐색을 진행하는 기법을 통해 문제를 풀 수도 있었다.
- 그러나 여기서 멈추지 않고, 스터디를 진행하며 집단 지성을 활용하여 더 최적화된 방법이 존재함을 발견했다.
- 문제의 특성을 잘 관찰하면, 최종적으로 “양수 그룹”과 “음수 그룹”으로 나누어 각각의 합 차이가 target과 일치해야 한다는 사실을 발견하게 된다.
- 이를 통해 문제를 덧셈만을 이용한 간결한 수학적 표현으로 전환할 수 있었으며, 이는 "부분집합 합(subset-sum)" 문제와 유사한 형태로 환원할 수 있다는 중요한 인사이트를 얻었다.
본 블로그에서는 다음 세 가지 접근을 단계적으로 제시할 것이다.
- 직관적이고 기본적인 DFS 완전 탐색 접근
- 결정 트리(decision tree)를 이용한 구조화된 모델링 접근
- 수학적 관찰을 기반으로 한 최적화된 덧셈 방식 접근
각 접근의 장단점과 구현상 차이를 함께 분석해보자.
💡 풀이
1. DFS 방식 풀이
DFS 방식은 재귀 호출을 이용해 각 숫자마다 '+' 또는 '–' 연산을 선택하면서 깊이 우선 탐색으로 가능한 모든 경우를 탐색하는 접근이다.
DFS로 이 문제를 해결하는 아이디어는 다음과 같다.
- 각 인덱스마다 두 가지 선택지가 존재한다:
- 숫자를 더하는 경우 (+numbers[index])
- 숫자를 빼는 경우 (-numbers[index])
- 이를 모든 숫자에 대해 재귀적으로 수행했을 때, 모든 선택이 끝난 상태에서 누적합이 target과 일치하는지를 확인한다.
- 일치하는 경우의 수만 카운트하여 최종적으로 답을 얻는다.
이렇게 각 선택의 결과는 독립적이고, 결정 순서를 유지한 채 누적합만 계산하면 되기 때문에 재귀적으로 간단히 구현할 수 있다.
주어진 코드의 동작을 [1, 1, 1, 1, 1], target = 3 예시로 구체적으로 살펴보자.
class Solution {
int target;
int[] numbers;
int count;
public int solution(int[] numbers, int target) {
this.target = target;
this.numbers = numbers;
this.count = 0;
dfs(0, 0);
return count;
}
public void dfs(int index, int sum){
if(index == numbers.length){
if(sum == target){
count++;
}
return;
}
dfs(index + 1, sum + numbers[index]);
dfs(index + 1, sum - numbers[index]);
}
}
이 코드에서 초기 상태는 다음과 같다.
index = 0, sum = 0
다음의 흐름을 따라 DFS가 수행된다. dfs(0 , 0)가 호출될 때의 데이터 흐름을 살펴보면 다음과 같다.
| 단계 | 재귀호출 ( dfs(index, sum) ) | 스택 깊이 | 누적합 계산식 | count 변화 |
| ① | dfs(0 , 0) | 0 | ― | 0 |
| ② | dfs(1 , 0+1) | 1 | 1 | 0 |
| ③ | dfs(2 , 1+1) | 2 | 2 | 0 |
| ④ | dfs(3 , 2+1) | 3 | 3 | 0 |
| ⑤ | dfs(4 , 3+1) | 4 | 4 | 0 |
| ⑥ | dfs(5 , 4-1) | 5 | 3 ⭑ hit | 1 |
| ⑦ | ⬅ 리턴 & 팝 | 4→0 | ― | 1 (고정) |
여기서 ①–⑥은 “++++-” 경로에 해당한다. ⑥에서 index == 5(리프) & sum == target → count++.
스택의 재귀 호출은 다음과 같이 이뤄질 것이다.
<!-- DFS 재귀 콜 스택 시각화 (bottom-up) : 경로 “++++-” -->
<svg width="260" height="380" viewBox="0 0 260 380"
xmlns="http://www.w3.org/2000/svg"
font-family="monospace" font-size="12" text-anchor="middle">
<!-- 배경 -->
<rect x="0" y="0" width="260" height="380" fill="#ffffff"/>
<!-- 프레임 간 y 간격 = 55 (아래 → 위) -->
<!-- 프레임 0 : 가장 먼저 쌓임 -->
<rect x="30" y="295" width="200" height="40" fill="#f0f8ff" stroke="#007acc"/>
<text x="130" y="321">index 0, sum 0</text>
<!-- 프레임 1 -->
<rect x="30" y="240" width="200" height="40" fill="#e8f6ff" stroke="#007acc"/>
<text x="130" y="266">index 1, sum 1</text>
<!-- 프레임 2 -->
<rect x="30" y="185" width="200" height="40" fill="#e0f0ff" stroke="#007acc"/>
<text x="130" y="211">index 2, sum 2</text>
<!-- 프레임 3 -->
<rect x="30" y="130" width="200" height="40" fill="#d8eaff" stroke="#007acc"/>
<text x="130" y="156">index 3, sum 3</text>
<!-- 프레임 4 -->
<rect x="30" y="75" width="200" height="40" fill="#d0e4ff" stroke="#007acc"/>
<text x="130" y="101">index 4, sum 4</text>
<!-- 프레임 5 (리프) -->
<rect x="30" y="20" width="200" height="40" fill="#c8deff" stroke="#007acc"/>
<text x="130" y="46">index 5, sum 3 ✅</text>
<!-- push 화살표들 (아래→위) -->
<defs>
<marker id="arrow" markerWidth="6" markerHeight="6" refX="5" refY="3"
orient="auto" markerUnits="strokeWidth">
<path d="M0,0 L6,3 L0,6 Z" fill="#007acc"/>
</marker>
</defs>
<line x1="130" y1="290" x2="130" y2="275" stroke="#007acc" stroke-width="2" marker-end="url(#arrow)"/>
<line x1="130" y1="235" x2="130" y2="220" stroke="#007acc" stroke-width="2" marker-end="url(#arrow)"/>
<line x1="130" y1="180" x2="130" y2="165" stroke="#007acc" stroke-width="2" marker-end="url(#arrow)"/>
<line x1="130" y1="125" x2="130" y2="110" stroke="#007acc" stroke-width="2" marker-end="url(#arrow)"/>
<line x1="130" y1="70" x2="130" y2="55" stroke="#007acc" stroke-width="2" marker-end="url(#arrow)"/>
<!-- 안내 -->
<text x="130" y="355" font-size="11" fill="#555">(리프 도달 후 pop & 백트래킹)</text>
</svg>
복잡도 및 특징으로 정리해보자.
| 항목 | 값 | 근거 |
| 시간 | O(2ⁿ) | 각 숫자당 ± 두 갈래 전부 방문 |
| 공간 | O(n) | 재귀 깊이 n ≤ 20 (Call Stack) |
| 코드 길이 | 20 줄 내외 | 의식적으로 “부호 선택-재귀 호출”만 구현 |
이렇게 간단한 DFS 를 이용한 완전 탐색으로도 쉽게 풀 수 있다.
다음 섹션에서는 “결정 트리 모델링”을 바탕으로 같은 문제를 구조적으로 바라보는 두 번째 해법을 살펴보자.
2. 결정 트리 모델링 접근
이번 접근은 문제를 결정 트리의 관점에서 구조적으로 이해하는 방식이다.
결정 트리로 문제를 바라보면, 각 숫자에서 '+'와 '-' 중 하나를 선택하는 두 가지 결정이 계속해서 내려지면서 완전한 이진 트리 구조를 이루게 된다. 즉, 인덱스별로 숫자에 부여할 부호를 결정하면서 가지(branch)가 생성되는 형태다. 이 모델링을 통해 "숫자 선택"이라는 복잡해 보이는 문제를 보다 명확한 "트리 탐색" 문제로 변환할 수 있다.
결정 트리 관점에서의 문제 이해는 다음과 같다.
- 트리의 각 레벨(level)은 숫자 배열의 인덱스를 나타낸다.
- 각 노드는 현재까지의 누적합(sum)을 나타낸다.
- 최종 레벨(리프 노드)에서는 누적합이 타겟 넘버(target)와 같은지를 체크하여 해당 리프의 개수를 센다.
다음은 스터디에서 팀원이 자바스크립트로 구현한 결정 트리 방식의 코드이다.
function solution(numbers, target) {
let sums = [0];
numbers.forEach(num => {
const next = [];
sums.forEach(s => {
next.push(s + num);
next.push(s - num);
});
sums = next;
});
return sums.filter(s => s === target).length;
}
이 자바스크립트 코드는 문제를 결정 트리의 구조로 해석하여 배열을 이용해 BFS 방식으로 모든 가능한 합을 탐색한다. 각 숫자를 순차적으로 처리하며, 이전 단계에서 계산한 누적합 배열(sums)의 모든 원소에 현재 숫자를 각각 더하고 빼는 과정을 반복하여 가능한 모든 경우를 생성한다.
단계적으로 살펴보면,
- sums 배열을 [0]으로 초기화하여 시작 상태로 둔다.
- 숫자 배열(numbers)을 앞에서부터 하나씩 순회하면서, 각 숫자마다 다음을 수행한다.
- 이전 단계에서 만들어진 누적합 배열 sums의 각 원소에 현재 숫자를 더하거나 빼서, 새로운 합을 생성하고 이를 새로운 배열(next)에 저장한다.
- 새로 생성된 배열 next를 다시 sums로 교체하여 다음 단계의 입력으로 사용한다.
- 위 과정을 마지막 숫자까지 반복한 후, 최종적으로 만들어진 sums 배열에 저장된 모든 경우의 합 중 target과 일치하는 값들의 개수를 세어 반환한다.
문제의 예시인 [1, 1, 1, 1, 1], target = 3로 작동을 살펴보자.
- 초기 상태: sums = [0]
- 첫 번째 숫자(1) 처리 후: sums = [+1, -1]
- 두 번째 숫자(1) 처리 후: sums = [+2, 0, 0, -2]
- 세 번째 숫자(1) 처리 후: sums = [+3, +1, +1, -1, +1, -1, -1, -3]
- 네 번째 숫자(1) 처리 후: sums = [+4, +2, +2, 0, +2, 0, 0, -2, +2, 0, 0, -2, 0, -2, -2, -4]
- 다섯 번째 숫자(1) 처리 후(최종): sums 배열에는 모든 조합의 합이 저장된다.
- 이 중 +3에 해당하는 원소는 총 5개가 존재한다. 따라서 최종 반환값은 5가 된다.
이 접근의 장점은 배열을 활용한 BFS로, 트리 탐색을 명확히 구조화하며 직관적으로 구현할 수 있다는 점이다.
다만, 생성된 배열(sums)의 크기가 단계마다 2배씩 커지므로 공간 복잡도는 DFS 대비 높다. (최대 O(2ⁿ)의 공간이 필요할 수 있다.)
이제 이러한 결정 트리 구조를 시각적으로 표현해보자.
간소화를 위해 [1, 1, 1]이라는 작은 입력을 예시로 들어보면 다음과 같다.
<svg width="440" height="200" xmlns="http://www.w3.org/2000/svg">
<style>
text { font-family: monospace; font-size: 13px; text-anchor: middle; }
line { stroke: #007acc; stroke-width: 1.5; }
circle { fill: #cce5ff; stroke: #007acc; stroke-width: 1.5; }
</style>
<!-- Level 0 -->
<circle cx="220" cy="20" r="15"/>
<text x="220" y="24">0</text>
<!-- Level 1 -->
<line x1="220" y1="35" x2="120" y2="75"/>
<line x1="220" y1="35" x2="320" y2="75"/>
<circle cx="120" cy="75" r="15"/>
<circle cx="320" cy="75" r="15"/>
<text x="120" y="79">-1</text>
<text x="320" y="79">+1</text>
<!-- Level 2 -->
<line x1="120" y1="90" x2="70" y2="130"/>
<line x1="120" y1="90" x2="170" y2="130"/>
<line x1="320" y1="90" x2="270" y2="130"/>
<line x1="320" y1="90" x2="370" y2="130"/>
<circle cx="70" cy="130" r="15"/>
<circle cx="170" cy="130" r="15"/>
<circle cx="270" cy="130" r="15"/>
<circle cx="370" cy="130" r="15"/>
<text x="70" y="134">-2</text>
<text x="170" y="134">0</text>
<text x="270" y="134">0</text>
<text x="370" y="134">+2</text>
<!-- Level 3 -->
<line x1="70" y1="145" x2="50" y2="185"/>
<line x1="70" y1="145" x2="90" y2="185"/>
<line x1="170" y1="145" x2="150" y2="185"/>
<line x1="170" y1="145" x2="190" y2="185"/>
<line x1="270" y1="145" x2="250" y2="185"/>
<line x1="270" y1="145" x2="290" y2="185"/>
<line x1="370" y1="145" x2="350" y2="185"/>
<line x1="370" y1="145" x2="390" y2="185"/>
<circle cx="50" cy="185" r="15"/>
<circle cx="90" cy="185" r="15"/>
<circle cx="150" cy="185" r="15"/>
<circle cx="190" cy="185" r="15"/>
<circle cx="250" cy="185" r="15"/>
<circle cx="290" cy="185" r="15"/>
<circle cx="350" cy="185" r="15"/>
<circle cx="390" cy="185" r="15"/>
<text x="50" y="189">-3</text>
<text x="90" y="189">-1</text>
<text x="150" y="189">-1</text>
<text x="190" y="189">+1</text>
<text x="250" y="189">-1</text>
<text x="290" y="189">+1</text>
<text x="350" y="189">+1</text>
<text x="390" y="189">+3</text>
</svg>
결정 트리에서 각 레벨이 배열의 각 숫자 선택을 나타내며, 각 원소에 '+'와 '-'를 부여하여 가능한 모든 합을 나타낸다. 리프 노드는 최종 가능한 합을 나타내며, 문제에서 제시된 숫자 배열이 더 길어지면 이 구조는 더 깊고 넓어지게 된다.
이러한 결정 트리 관점의 접근법은 명확한 구조를 제공한다는 점에서 장점이 있는 것 같다.
3. 수학적 관찰을 기반으로 한 최적화된 덧셈 방식 접근
이제까지는 '+' 또는 '–' 기호를 선택하는 방식으로 문제를 접근했다. 하지만, 스터디 과정에서 이런 물음을 갖게 되었다.
"이 문제를 프루닝(pruning)하여 더 최적화할 수 없을까?"
어떤 패턴이 있다고 느껴졌다.
문제를 자세히 살펴보면, 결국 숫자들을 '+' 부호를 붙인 그룹과 '–' 부호를 붙인 그룹으로 나누어 각각의 합을 구하는 형태로 바꿀 수 있다는 중요한 사실을 발견할 수 있다.
이를 좀 더 명확히 수학적으로 표현해 보자.
📌 원리 설명
원본 문제를 수식으로 다시 표현하면 다음과 같다.
각 숫자 $a_i$에 부호 $s_i \in {+1,-1}$ 를 붙여 다음 조건을 만족해야 한다.
$$
\sum_{i} s_i a_i = \text{target}
$$
모든 숫자 $a_i$의 합을 $S = \sum a_i$ 라 정의하면, 문제는 다음 두 가지 조건을 동시에 만족하는 두 그룹(양수 그룹의 합 $P$, 음수 그룹의 합 $N$)을 찾는 문제가 된다.
$$
P - N = \text{target}
$$
$$
P + N = S
$$
이 두 식을 이용해 아주 중요한 사실을 도출할 수 있다. 두 식을 더하면 다음과 같이 된다.
$$
(P - N) + (P + N) = \text{target} + S
$$
이를 정리하면 간단히 다음과 같은 핵심 공식이 나온다.
$$
2P = S + \text{target}
$$
즉, '+' 부호가 붙은 그룹의 합인 $P$는 다음과 같이 결정된다.
$$
P = \frac{S + \text{target}}{2}
$$
여기서 중요한 점은 $(S + \text{target})$ 값이 홀수라면, 처음부터 불가능하다는 의미다.
📌 간단한 예시로 이해하기
예를 들어 numbers가 [1, 1, 2]이고, target이 2라고 가정해보자.
- numbers의 전체 합 $S$ 는 $1 + 1 + 2 = 4$이다.
- 필요한 '+' 그룹의 합 $P$ 는 위 공식에 의해,
- $$
P = \frac{4 + 2}{2} = 3
$$
이제 문제는 "numbers에서 덧셈만 사용하여 합이 정확히 3이 되는 부분집합의 개수를 찾는 문제"로 바뀌었다.
실제로 \( \{1_{\text{(첫 번째)}},\,2\} \)와 \( \{1_{\text{(두 번째)}},\,2\} \)의 두 가지 경우가 존재하므로 답은 \(2\)이다.
그런데 여기서 여전히 이런 질문이 들 수 있다.
📌 전체값 S를 시그마 ai 라고 한 뒤, 2P = S + target을 증명한 논리가 이해가 안된다 이게 뭔말일까?
이 부분이 처음에 잘 이해가 안됐다. 그래서 좀 더 자세히 설명해보려고 한다.
다음과 같은 과정에서 그 이유를 명확히 알 수 있다.
이 문제는 숫자를 두 그룹으로 나누는 문제다. '+' 그룹과 '–' 그룹이라고 하자. 그러면 다음 두 가지 사실은 반드시 성립한다.
1. '+' 그룹의 합과 '–' 그룹의 합을 더하면 numbers의 전체 합 $S$와 같아진다. (당연한 사실)
$$
(+ \text{그룹의 합}) + (– \text{그룹의 합}) = S
$$
2. '+' 그룹의 합에서 '–' 그룹의 합을 빼면 목표값(target)이 된다. (문제의 조건)
$$
(+ \text{그룹의 합}) - (– \text{그룹의 합}) = \text{target}
$$
이 두 조건을 이용하면 '+' 그룹의 합을 좀 더 쉽게 구할 수 있다. 위 두 식을 좌변과 우변 각각 더해보자.
$$
(+ \text{그룹의 합}) + (+ \text{그룹의 합}) - (– \text{그룹의 합}) + (– \text{그룹의 합}) = S + \text{target}
$$
여기서 $(– \text{그룹의 합})$ 부분이 서로 상쇄되어 사라진다. 따라서 결국 다음과 같은 결과를 얻는다.
$$
2 \times (+ \text{그룹의 합}) = S + \text{target}
$$
이게 바로 $2P = S + \text{target}$ 이라는 식의 의미다.
즉, 전체 숫자를 두 그룹으로 나누었을 때 두 그룹의 합과 차에 대한 기본적인 수학적 관계에서 나온 결과라고 보면 된다.
지금까지의 내용을 그림으로 그려보면 다음과 같다.
📌 알겠는데... 무슨 의의가 있지?
- 뺄셈 연산을 하지 않고 덧셈만으로 문제를 단순화하여 해결할 수 있다.
- 문제를 간결한 수학적 형태로 전환함으로써 효율적인 DP 접근이 가능하다.
- 시간 복잡도가 $O(n \times P)$로 최적화된다. 이는 최대 약 2만 번의 연산으로 충분히 효율적이다.
다음으로 이 개념을 DP로 구체적으로 구현하는 방식을 살펴보자.
class Solution {
public int solution(int[] numbers, int target) {
int total = 0;
for (int n : numbers){
total += n;
}
int sumPlusTarget = total + target;
if ((sumPlusTarget & 1) == 1 || total < target){
return 0; // 불가능
}
int need = sumPlusTarget >> 1; // (S + target) / 2
int[] dp = new int[need + 1];
dp[0] = 1;
for (int num : numbers) {
for (int s = need; s >= num; --s) {
dp[s] += dp[s - num];
}
}
return dp[need];
}
}
위의 자바 코드를 단계별로 분석해 보면,
초기화 및 예외 처리
- 전체 합(total)을 구한다.
- 만약 (S + target) 값이 홀수이거나 total이 target보다 작다면 가능한 경우가 없으므로 즉시 0을 반환한다.
- need 변수는 수학적으로 도출한 공식 (S + target) / 2를 나타낸다.
DP 배열 생성 및 초기화
- dp[i]는 합이 i가 되는 경우의 수를 나타낸다.
- dp[0]을 1로 초기화해, 아무 원소도 선택하지 않은 경우를 기본값으로 설정한다.
DP 배열 갱신 과정
- 각 숫자 num에 대해 가능한 합 s를 역순으로 순회하면서 dp[s]에 dp[s - num]을 더한다.
- 역순으로 처리하는 이유는 같은 숫자가 여러 번 중복으로 사용되지 않도록 방지하기 위함이다.
예를 들어, numbers = [1, 1, 2], target = 2 → S = 4, need = 3 인 케이스를 살펴보면 아래와 같이 채워진다.
DP 과정을 통해 최종적으로 dp[3]의 값이 2가 되는 것을 볼 수 있다.
📌 검증
마지막으로 문제에 주어진 예시로 정말 제대로 답을 구하는 것이지 따져보자.
아래 표는 numbers = [4, 1, 2, 1] 에 대해 각 원소에 ‘+’ 또는 ‘–’ 부호를 붙인 모든 2⁴ = 16가지 경우를 나열한 것이다.
| # | 부호를 붙인 식 (+·− 순서: 4 1 2 1) | 플러스 쪽 합 P | 마이너스 쪽 합 N | 결과값 P − N | 타겟 4 달성? |
| 1 | +4 +1 +2 +1 | 8 | 0 | 8 | |
| 2 | +4 +1 +2 −1 | 7 | 1 | 6 | |
| 3 | +4 +1 −2 +1 | 6 | 2 | 4 | ✔ |
| 4 | +4 +1 −2 −1 | 5 | 3 | 2 | |
| 5 | +4 −1 +2 +1 | 7 | 1 | 6 | |
| 6 | +4 −1 +2 −1 | 6 | 2 | 4 | ✔ |
| 7 | +4 −1 −2 +1 | 5 | 3 | 2 | |
| 8 | +4 −1 −2 −1 | 4 | 4 | 0 | |
| 9 | −4 +1 +2 +1 | 4 | 4 | 0 | |
| 10 | −4 +1 +2 −1 | 3 | 5 | −2 | |
| 11 | −4 +1 −2 +1 | 2 | 6 | −4 | |
| 12 | −4 +1 −2 −1 | 1 | 7 | −6 | |
| 13 | −4 −1 +2 +1 | 3 | 5 | −2 | |
| 14 | −4 −1 +2 −1 | 2 | 6 | −4 | |
| 15 | −4 −1 −2 +1 | 1 | 7 | −6 | |
| 16 | −4 −1 −2 −1 | 0 | 8 | −8 |
- 전체 합 S=4+1+2+1=8S = 4+1+2+1 = 8
- 타겟 = 4
- 공식을 적용하면
\[
P = \frac{S + \mathrm{target}}{2}
= \frac{8 + 4}{2}
= 6
\]
\(\Longrightarrow\) “플러스 쪽 합이 6인 경우”가 곧 타겟을 만드는 경우와 1:1 대응.
표에서도 P = 6인 3-번, 6-번 두 줄만 결과가 4가 되어 ✔ 표시가 붙어 있는 것을 볼 수 있다.
따라서 이 예시의 정답은 2가지가 맞음을 확인할 수 있다.
이상으로 3가지 풀이 방식에 대해 살펴보았다.
같은 문제라도 관점을 달리하면 “탐색 → 구조화 → 수학화”로 진화하며 코드가 점점 짧고 탄탄해진다는 점이 흥미롭다.
추가로, 코테를 풀 때 확실히 "같이 풀면" 도움이 된다.
혼자 풀었으면 DFS 로 풀고 넘어갔을 문제지만 함께 풀면서 이거저거 Talking about을 하다보면 딥다이브하기 수월하고 뭐라도 나오게 된다.
문제를 푸는 데 그치지 말고, 왜 그렇게 풀 수 있는지 끝까지 파고들어 보자.
같이 할 수 있으면 Best.
그러면 다음 문제를 만났을 때 선택할 수 있는 도구 상자가 훨씬 넓어져 있을 것이다.
🚀 최종 제출 코드
1)
class Solution {
int target;
int[] numbers;
int count;
public int solution(int[] numbers, int target) {
this.target = target;
this.numbers = numbers;
this.count = 0;
dfs(0, 0);
return count;
}
public void dfs(int index, int sum){
if(index == numbers.length){
if(sum == target){
count++;
}
return;
}
dfs(index +1, sum + numbers[index]);
dfs(index +1, sum - numbers[index]);
}
}
2)
function solution(numbers, target) {
let sums = [0];
numbers.forEach(num => {
const next = [];
sums.forEach(s => {
next.push(s + num);
next.push(s - num);
});
sums = next;
});
return sums.filter(s => s === target).length;
}
3)
class Solution {
public int solution(int[] numbers, int target) {
int total = 0;
for (int n : numbers){
total += n;
}
int sumPlusTarget = total + target;
if ((sumPlusTarget & 1) == 1 || total < target){
return 0; // 불가능
}
int need = sumPlusTarget >> 1; // (S + target) / 2
int[] dp = new int[need + 1];
dp[0] = 1;
for (int num : numbers) {
for (int s = need; s >= num; --s) {
dp[s] += dp[s - num];
}
}
return dp[need];
}
}
