[백준] 2293번 동전 1 C++ 문제풀이

https://www.acmicpc.net/problem/2293

2293번: 동전 1

문제 풀이

DP문제라는걸 고려하고 문제 해결 방법을 고민하니 답이 금방 나왔다.

새롭게 경우의 수가 추가되는 경우를 생각해보니, dp[n] +  dp[n - 현재 사용한 동전의 종류 크기] 를 하면 새로운 dp[n] 값이 나온다.

우리가 궁금한 값은 dp[k] 이므로 dp[k]까지 배열을 돌려주면 된다.

소스 코드

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

vector<int> coin;
int dp[10001] = { 0 };

int main() {
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		int c;
		cin >> c;
		coin.push_back(c);
	}
	
	sort(coin.begin(), coin.end());
	
	dp[0] = 1;
	for (int i = 0; i < n; i++) { 
		int start = coin[i];
		for (int j = start; j <= k; j++) {
			dp[j] += dp[j - coin[i]];
		}
	}
    
	cout << dp[k] << '\n';
}