[C] 백준 - 2293번: 동전 1

5월 6일(월) - 다이나믹 프로그래밍(2293번)

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

---

최초 생각 정리

---

문제점

---

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int cost[101];
int dp[10001];

int main(void)
{
	int n, k;
	scanf("%d %d", &n, &k);

	for (int i = 0; i < n; i++)
	{
		scanf("%d", &cost[i]);
	}

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

	printf("%d", dp[k]);
	return 0;
}

---