[DP] Target Sum

양의 정수들로 이루어진 배열이 주어질 때 + 와 - 를 적절히 사용해서 특정 합 S 를 만들 수 있는 경우의 수를 찾는 문제

 

DP로 문제를 풀어보려한다.

배열에 있는 원소중 A그룹은 양수가 될 것이고, B그룹은 음수가 될 것이다.(배열에는 모두 양수인 정수이다)

따라서 A그룹은 우측 연산에 의해 (S+sum)/2로 표현된다

아래부터 A그룹은 target이라 부른다

 

일단 S가 sum보다 크거나 연산값이 홀수라면 답이 나올수 없으므로 경계값을 처리해준다

이후 findSubSet이라는 함수를 만들어 nums와 target을 넘겨준다

 

이 target은 양수가 될 원소들을 모두 합한 부분합이다

이것을 dp라는 배열로 만들것인데, dp[ i ]의 값은 target이 i가 되는 경우의 수이다.

 

i를 기준으로 Loop를 돌며 dp를 구해준다

코드에 주석으로도 달았지만, 예컨데 nums= [1, 3, 4], S=6이라고 해보자

이 경우 부분합(target)이 7이 될텐데, 7의 양수를 만들기 위해서는 dp[ 7-1 ] + dp [ 7-3 ] + dp[ 7-4 ]가 될 것이다

왜냐하면 dp[6]은 target이 6이 되는 경우의 수 인데, target을 7로 만들기위해선 1을 더해주는 방법 뿐이므로 이 시점까지 경우의 수가 dp[7]과 같다. 그러나 이는 3,4일때도 해당되는 설명이므로 모든 케이스대로 연산해주는 것이다.

이때 루프는 원소의 값보다 클떄까지만 돌려주면 된다.