음이 아닌 정수 목록 a1, a2, ..., an과 목표값 S가 주어졌다고 가정해 보겠습니다. 우리에게는 +와 -라는 두 가지 기호가 있으며, 각 정수마다 둘 중 하나를 선택해 부호를 지정해야 합니다. 이때 정수들의 합이 목표값 S와 같아지도록 기호를 배정하는 방법이 총 몇 가지인지 구하는 것이 이 문제의 목표입니다.
예를 들어 숫자가 [1,1,1,1,1]이고 S = 3이라면 출력은 5가 됩니다. 가능한 조합은 다음과 같습니다.
- -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
즉, 총 5가지 방법으로 기호를 배정할 수 있습니다.
문제 해결 접근 방법
이 문제는 동적 계획법(Dynamic Programming)과 재귀 호출을 활용하면 효율적으로 해결할 수 있습니다. 단계별 접근 방법은 다음과 같습니다.
- 크기가 21 × 2001인 dp 테이블을 생성하고 모든 값을 -1로 초기화합니다. 이 테이블은 메모이제이션(memoization)용으로 사용됩니다.
- 현재 위치 pos, 배열 v, 임시 합 tempSum, 목표합 S를 매개변수로 받는 재귀 함수 solve()를 정의합니다.
- pos가 배열 v의 크기와 같다면, tempSum이 s와 같을 때 true(1)를, 그렇지 않으면 false(0)를 반환합니다.
- dp[pos][tempSum + 1000]의 값이 -1이 아니라면 이미 계산된 결과이므로 해당 값을 그대로 반환합니다.
- ans := solve(pos + 1, v, tempSum - v[pos], s) + solve(pos + 1, v, tempSum + v[pos], s) — 현재 원소에 -를 붙이는 경우와 +를 붙이는 경우를 각각 탐색합니다.
- 계산된 ans를 dp[pos][tempSum + 1000]에 저장한 뒤 반환합니다.
- 메인 함수에서 solve(0, nums, 0, s) 형태로 호출하여 최종 결과를 얻습니다.
참고로 dp 테이블의 두 번째 차원 크기가 2001인 이유는 임시 합(tempSum)이 -1000부터 1000 사이의 값을 가질 수 있기 때문입니다. 배열 인덱스는 음수가 될 수 없으므로 tempSum에 1000을 더해 0~2000 범위의 인덱스로 변환하여 저장하는 방식입니다.
C++ 구현 예시
다음 구현 예시를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int dp[21][2001];
int solve(int pos, vector <int> v, int tempSum, int s){
if(pos == v.size()){
return s == tempSum;
}
if(dp[pos][tempSum+1000]!=-1)return dp[pos][tempSum+1000];
int ans = solve(pos+1,v,tempSum-v[pos],s) +solve(pos+1,v,tempSum+v[pos],s);
dp[pos][tempSum+1000] = ans;
return ans;
}
int findTargetSumWays(vector<int>& nums, int s) {
int n = nums.size();
if(s>1000)return 0;
for(int i =0;i<21;i++){
for(int j =0;j<2001;j++){
dp[i][j] = -1;
}
}
return solve(0,nums,0,s);
}
};
main(){
Solution ob;
vector<int> v = {1,1,1,1,1};
cout << ob.findTargetSumWays(v, 3);
}입력
[1,1,1,1,1] 3
출력
5