[Leetcode][923] 3Sum With Multiplicity

문제 : leetcode.com/problems/3sum-with-multiplicity/

---

 

0이상 100이하의 정수를 가지는 배열 arr이 주어진다.

서로다른 원소 3개를 더한 값이 target이 되는 조합의 개수를 구하라.

---

배낭문제로 구할 수 있다.

dp[target][cnt] = cnt 개의 원소들을 합해서 target 을 만들 수 있는 경우의 수.

 

i 번째 원소(num)를 기준으로 dp 배열을 갱신해나간다.

num + x = target 이라 가정하면 num에 x를 더하면 target을 만들 수 있으므로, x의 경우의 수로 target 인덱스를 갱신할 수 있다.

위의 식에서 num을 우항으로 옮기면 x = target - num이 되므로 

dp[target][cnt+1] += dp[target-num][cnt] 가 된다.

num으로 갱신되기 전의 dp값을 좌항에 더해야 하므로 target, cnt 값은 큰 값부터 탐색해야 한다.

 

시간복잡도는 N = |arr|, M = target이라 했을 때, O(3NM).

공간복잡도는 O(4M)

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/923.%203Sum%20With%20Multiplicity.cpp