CSES 3. Money Sum (1745)

출처: https://cses.fi/problemset/task/1745

---

문제 설명

You have n coins with certain values. Your task is to find all money sums you can create using these coins.

입력 

The first input line has an integer n: the number of coins.

The next line has n integers x1,x2,…,xn : the values of the coins.

출력

First print an integer k: the number of distinct money sums.

After this, print all possible sums in increasing order.

입력 예

4
4 2 5 2

출력 예

9
2 4 5 6 7 8 9 11 13

제약조건

1<= n <=100

1<= x_i <= 1000

---

문제 풀이

가능한 최대값은 100*1000 (max_n, max_xi) 이다. 가능한 최대값과 같은 크기의 boolean 배열을 만든다. 각 코인마다 값들을 더해가면서 falst->true 로 변경한다. 만들어진 배열에서 true 경우를 세고, dp[u] == true 이면, u가 가능한 값이 된다.

프로그램 내용

vector<bool> dp(n*1000+1);
...
for (int c : coins) 
{
	for (int i = dp.size() - 1; i > 0; i--) 
	{
            if (dp[i]) 
                dp[i + c] = 1; 
            d[c] = 1; 
	}
}
...

 

Dynamic Programming ( link )