문제 개요
음수가 아닌 정수로 이루어진 리스트 nums와 정수 target이 주어집니다. 리스트의 각 숫자 앞에 + 또는 - 기호를 배치하여 전체 수식의 결과가 target과 같아지도록 만드는 방법이 총 몇 가지인지 구하는 것이 목표입니다.
예를 들어 입력이 nums = [2, 3, 3, 3, 2], target = 9라고 해보겠습니다. 이때 정답은 2입니다.
- -2 + 3 + 3 + 3 + 2 = 9
- 2 + 3 + 3 + 3 - 2 = 9
목표값을 만족하는 조합이 위의 두 가지뿐이기 때문입니다.
핵심 아이디어: 부분 집합 합 문제로 변환
+ 기호가 붙은 숫자들의 합을 P, - 기호가 붙은 숫자들의 합을 N이라 하면 다음 두 식이 성립합니다.
- P + N = s (전체 숫자의 합)
- P - N = target
두 식을 더하면 P = (s + target) / 2임을 알 수 있습니다. 즉, 이 문제는 "합이 (s + target) / 2가 되는 부분 집합의 개수를 세는" 고전적인 부분 집합 합(Subset Sum) 카운팅 문제로 변환할 수 있으며, 동적 계획법(DP)으로 효율적으로 해결됩니다.
알고리즘 단계
- s := nums에 있는 모든 숫자의 합
- (s + target)이 홀수이거나 target > s이면 0을 반환 (조건을 만족하는 배치가 존재할 수 없음)
- W := (s + target) / 2의 몫
- dp1 := 크기가 (W + 1)이고 0으로 채워진 리스트, dp1[0] := 1 (아무것도 선택하지 않는 경우 1가지)
- dp2 := 크기가 (W + 1)이고 0으로 채워진 임시 리스트
- nums의 각 숫자에 대해:
- j를 0부터 W까지 순회하며, j >= nums[i]이면 dp2[j] += dp1[j - nums[i]]
- 순회 후 dp1[j] += dp2[j]로 결과를 누적하고 dp2[j]를 0으로 초기화
- dp1의 마지막 원소(dp1[W])를 반환
Python 구현 예제
class Solution:
def solve(self, nums, target):
s = sum(nums)
# (s + target)이 홀수이거나 target이 s보다 크면 답은 0
if (s + target) % 2 != 0 or target > s:
return 0
W = (s + target) // 2
dp1 = [0] * (W + 1)
dp1[0] = 1
dp2 = [0] * (W + 1)
for num in nums:
for j in range(W + 1):
if j >= num:
dp2[j] += dp1[j - num]
for j in range(W + 1):
dp1[j] += dp2[j]
dp2[j] = 0
return dp1[-1]
ob = Solution()
nums = [2, 3, 3, 3, 2]
target = 9
print(ob.solve(nums, target))
입력
[2, 3, 3, 3, 2], 9
출력
2
복잡도 분석
시간 복잡도: O(n × W) — 각 숫자마다 DP 테이블을 한 번씩 순회합니다.
공간 복잡도: O(W) — 크기가 W + 1인 두 개의 배열만 사용하므로 메모리 사용량이 일정하게 유지됩니다.