[C++] 백준 2239 동전1

 
#include <iostream>
#include <vector>
 
int main() 
{
	int n = 0;
	int k = 0;
 
	std::cin >> n >> k;
	std::vector<int> arr(n, 0);
	std::vector<int> dp(k + 1, 0);
 
	for (int i = 0; i < n; ++i)
	{
		std::cin >> arr[i];
	}
 
	// 동전 아무것도 선택 X
	dp[0] = 1;	
 
	for (int i = 0; i < n; ++i) 
	{
		int iNumber = arr[i];
 
		for (int j = iNumber; j <= k; ++j)
		{
			// arr[i] 만큼 차이나는 것을 추가로 입력 
			// arr[i]가 2일 경우 3 -> 5 // 5 -> 7 이런 갯수를 추가로 계속해서 입력
			dp[j] += dp[j - iNumber];
		}
	}
 
	std::cout << dp[k];
 
	return 0;
}

1. dp에 arr[i]만큼 차이나는 것들로 채운다.

2. arr[i]가 가능한 만큼 더해준다.