2293(dp)

첫인상

수학 문제로 풀면 어떨까 하고 생각했다

문제상황

고려할게 너무 너무 많고 정확히는 모르겠지만 시간 초과가 날 것 같다

풀이

dp로 풀기로 결정하고 코인가격을 x 라고 했을 때 변수를 가격으로 두고 dp[n] += dp[n - x] 를 점화식으로 두고 풀었다.

코드

#include<iostream>
using namespace std;

int dp[10005];
int nums[105];
int n, k;

void input() {
	cin >> n >> k;

	for (int i = 1; i <= n; i++) {
		cin >> nums[i];
	}
}

void solve() {
	dp[0] = 1;

	for (int i = 1; i <= n; i++) {
		int x = nums[i];

		for (int j = x; j <= k; j++) {
			dp[j] += dp[j - x];
		}
	}

	cout << dp[k];
}

int main() {
	input();
	solve();
}