출처: 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 )
'CSES' 카테고리의 다른 글
CSES 6. Tree Algorithms (0) | 2021.07.21 |
---|---|
CSES 5. Range Queries (0) | 2021.07.21 |
CSES 3. Rectangle Cutting (1744) (0) | 2020.07.28 |
CSES 3. Edit Distance (1639) (0) | 2020.03.18 |
CSES 4. Road Reparation (1675) (0) | 2020.01.20 |