백준 2293 동전 1, c++

 

 

 

작성한 코드는 다음과 같다.

다이나믹 프로그래밍을 사용하여 구현하는 문제였다.

첫번째 for문에서는 입력받은 n개의 경우로 만들 수 있는 경우의 수를 세주고

두번째 for문에서는 1부터 k까지를 몇가지 방식으로 만들 수 있는 지를 계산한다.

최종은 dp[k]를 출력한다.

 

예를 들어

0부터 k까지의 모든 수를, 1로 만들 수 있는 경우의 수를 먼저 (dp배열에) 계산하고

0부터 k까지의 모든 수를, 2까지 추가됐을 때 만들 수 있는 경우의 수를 기존 (dp배열에) 에 더해주고

0부터 k까지의 모든 수를, 5까지 추가됐을 때 만들 수 있는 경우의 수를 기존 (dp배열에) 에 더해주는 방식을 사용한다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> arr(n);
	vector<int> dp(k+1);
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	dp[0] = 1;	
	for (int i = 0; i < n; i++) { 
		for (int j = arr[i]; j <= k; j++) { 
			dp[j] +=dp[j - arr[i]];
		}
	}

	cout<<dp[k]<<endl;
	return 0;
}