[LeetCode] 2902. Count of Sub-Multisets With Bounded Sum (C++)

문제

https://leetcode.com/problems/count-of-sub-multisets-with-bounded-sum/description/

Count of Sub-Multisets With Bounded Sum - LeetCode

 

 

풀이

 

난이도: Hard

 

 

해설을 봐도 이해하기 힘든 문제였다.

 

 

 

 

 

 

일단 두 가지 해설을 참고하였다.

해설1,  해설2

 

 

dp로 해결하기 위해서 일단, 모든 집합에 보이지 않는 0이 들어간다고 생각하자.

 

{0,1}, {0,2}, {0,4}, {0,2,2}... 이런 식이다.

이를 위해 dp[0] = 1로 세팅한다.

 

 

 

 

dp[value]는 해당 value를 만들 수 있는 subset의 개수이다.

 

dp[value]는 어떻게 구할 수 있을까?

 

하나의 element와 그 개수 cnt를 구해두었을 때, dp[value] 는 다음과 같이 구해진다.

dp[value] += dp[value - element *1 ] + dp[value - element*2 ]  + dp[value - element*3 ] + ... +  + dp[value - element*cnt ]

 

dp[value - element *1 ]는 ( value - element *1) 를 만드는 subset들에 element 하나를 추가하여

{element, ...}인 subset들을 새로를 만들고,

 

dp[value - element *2 ]는 (value - element *2) 를 만드는 subset들에 element 두개를 추가하여

{element, element, ...}인 subset들을 새로를 만든다는 의미이다.

 

예를 들어 위의 예제처럼 2는 2개가 있다면, 아래와 같이 dp를 구할 수 있다.

dp[5] += dp[3] + dp[1]      => {2, (3을 만드는subset)} , {2, 2, (1을 만드는subset)} 추가

dp[4] += dp[2] + dp[0]      => {2, (2를 만드는subset)} , {2, 2, (0을 만드는subset)} 추가

dp[3] += dp[1]                  => {2, (1을 만드는subset)} 추가

dp[2] += dp[0]                  => {2, (0을 만드는subset)} 추가

 

 

 이때 dp는 큰 수부터 차례대로 구해야 하는데, 만약 작은 수부터 구한다면,

dp[2]에서 구한 값이 다시 dp[4]에서 사용되면서, cnt 이상의 개수를 사용하서 틀린 값이 구해진다.

 

 

 

 

 

이처럼 구해 나간 다음, dp[l]에서 dp[r]까지의 값을 합치면 되는데 arr에 0이 한 개 이상 있다면 지금까지 만든 모든 subset에 0을 추가해서 새로운 subset을 만들 수 있다.

 

 

예를 들어 다음과 같을 때는

Input: nums = [0,0,1,2,2,3], l = 6, r = 6
Explanation: subset of nums that has a sum of 6 is {1, 2, 3}.

여기에 0이 하나 추가된 {0,1,2,3}와 두 개 추가된 {0,0,1,2,3}가 추가로 생성된다.

 

 

따라서 최종적으로 구한 개수에 (0의 개수 +1) 만큼 곱해주자.

 

 

 

 

 

코드

 

element의 개수들은 unordered_map로 간단히 구했는데,

unordered_map의 iterator는 key가 작은 순서대 진행되므로 sorting은 따로 필요 없다.

 

 

 

그런데 문제는 이렇게 구현한 코드도 시간 내에 겨우 동작한다. (테스트를 통과해도 너무 오래 걸린다고 오답처리된다...)

따라서 최대한 효율적으로 최적화해야 한다.

 

sum_so_far이라는 값을 추가해서, 답을 구하는 데 사용된 elements들의 합이 r보다 작다면, sum_so_far부터 시작하도록 최적화했다.